View Single Post
Old 2003-03-07, 23:44   #1
gbvalor
 
gbvalor's Avatar
 
Aug 2002

3×37 Posts
Default About trial factoring

Hi all,

It has been a hard week and now is too late in Europe, so forgive me if I write something wrong. Here you are ...

Is well know that for a prime p, if the Mersenne Number

Mp = 2^p - 1

is not prime and thus it has factors, they are in the form

F = k * q + 1

where q = 2 * p

I'm wonder whether we can take any advantage of this special form of
the Mersenne number factors in Trial factoring task, specially when
candidate factors are longer than 64 bits.

For trial factoring, once we have a candidate for factor passing the filters:

1) F=+1 or -1 (mod 8 )

2) F have no small factors

We have to make modular exponentiation (mod F). And see whether

2^p = 1 (mod F)

The most expensive task in the modular exponentiation is the modular
square, i. e. to compute

y = x * x (mod F)

If we write x < F in the form

x = a1 * q + a0, a0 < q, a1 < k (1)

it looks like a semi representation in base q . Note than a1 can be high
enough (a1 >> q).

We can write

x * x = (a1 * ((a1 * q) + 2 * a0 ))* q + a0 * a0; (2)

or

x * x = (a1 * a1 * q + 2 * a0 * a1 ) * q + a0 * a0; (3)



OTOH if we want to compute

(A * q) mod F = A * q mod ( k * q + 1) =

= r * q - c

where

r = A mod k
c = A / k (integer division)

i. e.

A = c * k + r

Usually, c can be computed fast in a FPU.

even more, we can see

A * q^2 mod F = (A * q) * q mod F =
= ((A * q) (mod F)) * q) (mod F) = (B * q) (mod F) =
= ((r0 * q - c0) * q) (mod F) =
= (r1 * q - c1) (4)

where A = c0 * k + r0
B = r0 * q - c0 = c1 * k + r1

Then to compute (3) we would need to perform three k-modulo and a
q-modulo plus some more work. Let's see and example. Suposse candidate
F having 70 bits, 25 bits for q and the remaining 45 to k.

What we need to do:

I) C = a1 * a1 * q^2 mod F

This requires
i ) 45 * 45 bits square x = (a1 * a1)
ii) compute c0 = int (x / k)
iii) compute r0 = x mod k
iv) compute B = r0 * q - c0 (70 bits arithmetic)
v) compute c1 = int (B / k)
vi) compute r1 = B mod k

II) D = 2 * a0 * a1 * q mod F
i) a 26 * 45 bits mul y = 2 * a0 * a1
ii) compute c2 = int (y / k)
iii) compute r2 = y mod k

III) a0 * a0
i) compute c3 = (a0 * a0 - c1 - c2) mod q
ii) compute r3 = int (a0 * a0 - c1 - c2) / q

IV) final
i) C = (r1 + r2 + r3) * q + c3
ii) normalization


Is a long list of things to do, but I don't know if is a lot of
work compared with multiprecision arithmetic we would make other way
The proposed scheme only uses modular arithmetic for lengths where
there fast and optimized algorithms.

Is this a cracy or wrong idea?. May be.

Guillermo Ballester Valor
gbvalor is offline   Reply With Quote