quickQuiz #1 (maths)
•
19 Nov 2007, 22:49
•
Journals
Factorize 25805307988219.
Also tell me your methods ( I'm curious )
Results:
Meez won the cookie!
Sweetooth used google.
I was lazy and used the linux program called factor:
user@host ~ $ factor 25805307988219
25805307988219: 1212851 21276569
Also tell me your methods ( I'm curious )
Results:
Meez won the cookie!
Sweetooth used google.
I was lazy and used the linux program called factor:
user@host ~ $ factor 25805307988219
25805307988219: 1212851 21276569
:D .... nice try for journal xD
gl
1212851 and 21276569
cant be bothered
the prime factors (of 25805307988219) are 1212851 and 21276569
How did u do it?
hi meez btw
keep telling myself I'll put effort into programing, but I never get round to it
found that it is composite. Pick a random start x(0) with
1 < x(0) < N. For i = 1, 2, 3, ..., compute:
x(i) = x(i-1)^2 - 1 (mod N)
x(2*i-1) = x(2*i-2)^2 - 1 (mod N)
x(2*i) = x(2*i-1)^2 - 1 (mod N)
d(i) = GCD(N, x[2*i]-x)
If d(i) = 1, increment i and repeat the computation.
If 1 < d(i) < N, then you have split N into two factors:
N = d(i)*[N/d(i)].
If d(i) = N, pick a new value of x(0) and begin the process anew.
Once you have split N into two parts, you have to test them both to
see if they are prime or composite, and repeat the process on the
composite parts.
Example: N = 1037. Pick the random start x(0) = 44.
i x(i) x(2*i) d(i)
0 44 44 --
1 898 654 61
and, sure enough, N = 61*17, and both factors are prime.
With your example N = 2211280 and the start x(0) = 12843, 5 would
appear as a factor after 1 step, 16 after 2 steps, and 211 after 13
steps, leaving 131 (which would have appeared at the 14th step).
If we instead start with x(0) = 1033994, the factor of 131 appears on
the first step, and on the second step, we get 40*422, both parts
composite.
Usually to find a factor P takes about sqrt(P) steps. We were lucky in
the first example, needing only one step. With your method, it takes
P/ln(P) steps, and luck plays no part. Pollard Rho steps are more
complicated than your divisions, however. The explanation for why this
works is not within the scope of this note, but involves some
fascinating ideas from number theory and probability theory.
http://mathforum.org/library/drmath/view/51544.html
I wanted to see how the community responds to a quick quiz like this. Furthermore, I was curios on the various methods people could think of.
but if u stay here now i can wrote 1 more task for today :)
life is life bitzeeez