Verifying factors...

[jocelynl]

:)to test a factor, all you need is the same algorythm that they use in prime95. you wish to test 2^9835211-1, so take the binary number of 9835211.
110100110100100001101001

here is a small basic programm

m=9835211
Factor=36293798558667431

fnModulo(Factor,m)
modulo=1
length=len(m)
for x=length to 0 step -1
modulo=(modulo*modulo) mod Factor
if bit(x,m)=1 then modulo=(2*modulo) mod Factor
next
return(modulo)

if modulo=1 then 36293798558667431 is a factor of 9835211
very fast algorythm.

[Daffy]

Originally Posted by alpertron

That is, as a first step, you could do the the following:

Q <- 1
do 9835211 times: Q <- Q * 2 mod 36293798558667431
Q <- Q - 1

In this case you should get zero, so you found a factor.

Something very simple you could do and I will take an example:

2^15 mod 6 = (2^3)^5 mod 6 = 8^5 mod 6 = 2^5 mod 6 = 2^3 * 2^2 mod 6 = 2 * 4 mod 6 = 2

2^17 mod 7 = (2^3)^5 * 2^2 mod 7 = 8^5 * 4 mod 7 = 1^5 * 4 mod 7 = 4 mod 7 = 4


This works for all values: X mod Y can be calculated very fast this way.

There is no need to multiply 9835211 times q * 2 modulo ......

You just need to compute smaller values. I used this formula.

X*Y mod Z = XX * YY mod Z where XX = X mod Z and YY = Y mod Z.

The "difficult" part is to do it efficiently in the least amount of computations. But even if you waste a few, no big deal. It's still much faster. This is maybe what the other tools are doing.

[toferc]

jocelynl has got it quite right. It might help to look at the GIMPS home page quickie description of the algorithm at

http://www.mersenne.org/math.htm

under "Trial Factoring".

Chris Caldwell's Prime Pages glossary has an entry for the Binary Exponentiation algorithm upon which this is based:

http://primes.utm.edu/glossary/page.php?sort=BinaryExponentiation

HTH