h a l f b a k e r yA few slices short of a loaf.
add, search, annotate, link, view, overview, recent, by name, random
news, help, about, links, report a problem
browse anonymously,
or get an account
and write.
register,
|
|
|
Finding factors
A small piece of script that makes decimal factors systematic | |
------NOTICE-------
I have decided to explain all the questions that I can explain about this project. I add some explanation every now and then. This subject is still under my mental processing and examination.
I begin with explaining why I have started it from "x = int(sqrt(code));". The fact
is that (NaturalNumberA) * (RationalNumberA) = x = (RationalNumberB) * (NaturalNumberB).
This means that calculations doesn't have to be done twice. When "x = int(sqrt(code));" then (NaturalNumberB) inclines by 1 and decimal value of (RationalNumberB) is added to the sheet that grows along the curve.
About the value of "limit = x * 2;". For some reason this value is valid only when limit is bigger than x * 1. When the limit is 2 it shows the most interesting area of integers. Most likely the factors are close to that inflection point area.
----------------------
These days RSA is the normal decrypting form. It bases on the fact that factors of big numbers are very difficult to find. I have made some research about systematic decimals.There are two ways to script these same indicators, and I'm about to present you only one of them.
For visualizing this script you need SciLab, that is a free math program.
P.S.
This article is about showing that decimals of factors are changing according to a system that might be able to be described with a function. I add few images to illustrate what I mean:
First image is without code:
if next > prev + gap then level = level - 1; elseif prev > next + gap then level= level + 1; end,
http://pekkanen.brinkster.net/wav.gif
It looks like a zigzag, and therefore we have to add gap =0.5; and " if next > prev + gap then level = level - 1; elseif prev > next + gap then level= level + 1; end,"
http://pekkanen.brinkster.net/dec.gif
As a result we get a pretty line that looks like a peak.
I haven't changed the integer type so maximum values that can be processed without modifications are according to a float interger size.
Here after the line begins the code that you have to insert to editor.
-----------------------
code=12345677;
x = int(sqrt(code));
limit = x * 2;
division = code / x;
rounding = int(division);
final = division - rounding;
sheet($+1) = final;
prev = final;
x = x + 1;
gap = 0.5;
level = 0;
while x <= limit,
division = code / x,
rounding = int(division),
next = division - rounding,
if next > prev + gap then level = level - 1; elseif prev > next + gap then level= level + 1; end,
final = next + level,
sheet($+1) = final,
x = x + 1,
prev = next,
end,
clf();
plot2d (sheet);
--------------------- ends here -----
SciLab
http://www.scilab.org/
A free math tool [Thrust, Jan 09 2009]
GAP
http://www.gap-system.org/
Another free tool that can be used to play with large integers. [Vernon, Jan 09 2009]
Normal decimal wave
http://pekkanen.brinkster.net/wav.gif
This wave is produced by plain factorization [Thrust, Jan 09 2009]
Filtrated decimal wave
http://pekkanen.brinkster.net/dec.gif
Filtrated wave is always same shaped, only the size alters according to the "code" size. [Thrust, Jan 09 2009]
ZigZag arc
http://pekkanen.brinkster.net/saw.gif
This is clear demonstration where (if next > prev + gap then level = level - 1; elseif prev > next + gap then level= level + 1; end,) is needed for a full arc [Thrust, Jan 12 2009]
Finished project "Factorizing with Visual analysis"
http://pekkanen.bri...t/factors/index.htm
This site is about the same subject, but better explained. [Thrust, Jul 28 2010]
[link]
|
| |
I think that, to work here at the HB, you need to explain
rather than just list code. How does it work, why does it
work, why is it good, and does it involve custard? Those are
the main considerations here. |
|
| |
Looking at the code, it seems like a fairly naive brute-force effort, with a limit applied at the upper boundary, it scans through all iterations of x from 1 to the limit, checking whether each iteration is one half of a no-remainder factor-pair. This is fine on small numbers like 12345677, but proper RSA factoring occurs on much bigger numbers - I tried figuring this out a while back, but an iterative approach takes awfully long when you have to do it 1x10^250 times - or maybe I've missed something vital - I'd welcome a little explanation. |
|
| |
Not a method of locating debt recovery services then? |
|
| |
I say we give [Thrust] a break. It is not often that a newbie posts a HOW, without explanation of WHAT. Usually they are all WHAT and lack a HOW. With the exception of the [Treon],[<i-forget-now>] and [beanangel] ensamble. Then there is always [el dueno ~ el dueno]. |
|
| |
It is obvious that [Thrust] has been reading the posts for a while and decided, with associated angst, to post here. |
|
| |
[Thrust], ease up on the cut and give us a bit more thrust. |
|
| |
I could go into a diatribe of what you are doing in your code, but I can't tell you where... |
|
| |
Most factorisation sieves employ a "process of elimination" methodology. They have to because no specific pattern exists amongst the primes. The simplest, the Sieve of Eratosthenes, basically eliminates the composite numbers one prime at a time. Other sieves eliminate vast sections of the integers by eliminating numbers of a certain form. e.g. 6k+1 and 6k+5. there are more like this depending on computational resources. The common factor of these sieves is that they examine integers less than equal to the sqrt(N) where N is the number to be factorised. Your system seems to be taking the numbers greater than the sqrt(N) and examining their decimal residues or remainders. |
|
| |
Is basically (code)/(sqrt(code)) = (code)^(1-0.5)=(code)^0.5. |
|
| |
It is quite probable that you have come upon an excruciatingly beautiful pattern in the graphs you plot. You are wondering if you are close to the Riemann Hypothesis with your introduction of the //gap=0.5//. |
|
| |
Please tell us why mapping residues of > N/sqrt(N)+x(i) is making you so happy. Otherwise I could fill a whole halfbakery with why it is not. I would rather like to spend some time earning money, seeing as the banks have gone to the dogs... |
|
| |
Pointy curve tells that it can be replaced with a function that finds factors or if it is a prime number. I started from x = int(sqrt(code)) therefore that it doesn't count twice the values. It is possible to replace x = 1 and let it count to code "limit = code". |
|
| |
Excuse me for my language, I'm finnish so it's a bit difficult to me to express what I think. |
|
| |
It should work with any number, only difference would be in size of the curve. I suggest to test different "codes" with SciLab and it draws same shaped but different sized curves. One problem is that I don't know how to enter bigger that float integer numbers to SciLab. SciLab rounds the value if it's too big. If anyone could tell me how to use bigger values I'd appreciate it. |
|
| |
I got no much scripting skills. I appreciate all the help you might give me. SciLab just felt easier to use for visualization. |
|
| |
The GAP thing I linked is a programming language and "run" environment that is built from the ground up to handle large integers, even if they are a million digits long. Heh, in playing with it I have yet to find a way to make it easily display any value that has a decimal point in it; it really wants to do integers only. (Oh, fractions of the ordinary sort are easy, since they can always be expressed as Integer1/Integer2.) |
|
| |
What I meant with gap was to add one integer if the change of value was 0.5. It tells that the curve continues above or below the next integer.
One thing I like to know, is there any people who could help me to define the curve as a function? |
|
| |
x = int(sqrt(code)); is needed for keeping the same form of the curve and lack of counting double (1*x and x*1). Is this really so dead fish as it seems to be? I guess it doesn't help anyone braking RSA codes as it is... |
|
| |
Check out the image of zigzag arc that visualizes the problem that is corrected with (if next > prev + gap then level = level - 1; elseif prev > next + gap then level= level + 1; end,) |
|
| |
Check out the subjects introduction |
|
| |
Just for fun, here's a stupid useless intriguing math trick. Start with the number 1234567; it has two prime factors. |
|
| |
Its square root is 1111-and-an-irration; let's take the integer part and call it "r". |
|
| |
We know that one factor "f" of 1234567 is less than "r" by some unknown value we can call "x", so "f=r-x". |
|
| |
And we know that its other factor "F" is larger than "r" by some unknown value we can call "y", so "F=r+y". |
|
| |
Let us now take our "r", 1111, and compare its square, which is 1234321, with our original value 1234567; the difference between them is 246. |
|
| |
It happens that "x"=984.
It's also just a coincidence. Enjoy! |
|
| |
This value 12345677 was a plain example. This algorithm creates a curve even if it would be a random number. |
|
| |
I added again some explanations for the project. All the responses are welcome ecpecially those that are against my conclusions.
I would appreciate if you people told me how to fix my subject to be more proper. My method for making projects is synthesis type of process. I examine what kind of barriers arise against a beautiful and logical conclusion and fix those parts. |
|
| |
As I have stated, factoring is a trivial procedure. Factoring in polynomial time is a little more impossible. I will, over the course of the weekend, examine your contribution to ascertain whether it is valuable in terms of complexity reduction. |
|
| |
There is the analogy with monkeys and typewriters here. Given infinite monkeys and sufficient time, or sufficient monkeys and infinite time, they will type out all the primes. The problem is doing it in the least amount of time, with the least amount of monkeys. That is why P v NP is a Clay problem, and factoring large primes is not. |
|
| |
There is the well recognised case of: |
|
| |
If, and only if, the Goldbach conjecture is true: |
|
| |
1) for any integer n, there is an integer d, where n-d is prime, and n+d is prime. (n and d are co-prime). (n-d)+(n+d)=2n. |
|
| |
2) Then n-d=p, and n+d=q, from above. |
|
| |
3) Therefore (n-d)(n+d)=pq=n^2-d^2. |
|
| |
4) Every product of two primes is the difference of two squares. |
|
| |
5) Further, all n has a d, so every pq is represented by all n^2-d^2, as long as n and d are co-prime. |
|
| |
6) From this: If n and d are co-prime (have no common prime factors), then they represent pq. |
|
| |
7) this seems to be what is happening in the above idea. Unfortunately, it relies on Goldbach being true... |
|
| |
Check out link to an imagae "Filtrated decimal wave". Since this wave is the always same, except for the size, I bet it is possible to be replaced with a function formula. This means that only few basic values are needed to create this. I'd like to hear your opinions about if I am wrong about it, thank you. |
|
| |
If the curve can be expressed as a Bezier curve, it should make counting of the huge integer values much easier and in a finite time. Check out the image links if you haven't looked them yet. |
|
| |
(1.) x = int(sqrt(code));
This script is made for the most prominent values and reducing double values such as:
integer1 * integer2 = integer2 * integer1 |
|
| |
(2. ) limit = x * 2;
This value can be x * y;
where y >1 |
|
| |
Check out the latest link for a whole project in a html form. |
|
| |
What iff i told you the Goldbach Conjecture is true... |
|
| |