Thread: P-1 question
View Single Post
Old 2011-10-06, 13:23   #2
Romulan Interpreter
LaurV's Avatar
Jun 2011

223408 Posts

When you raise 3E it could happen that the order of 3 is smaller then 2kp/h, with h the highest factor of k. This happens often.

Edit: assume you want to factor M11=2047. You pick a B1 and B2 both equal with 2. You will not find any factor by rising 3 at the power of 2. You have to raise 3 at a power which is a multiple of 88/2p to find any factor, as the order of 3 in 2047 is 88, (388=1 mod 2047) which is 2*4*11. So your B1 and B2 have to be slightly larger, 4 would be enough. But there is nothing magic in that 3. Any other number below 2047 would suffice, and assuming you pick from a magic hat the number 622, then 622^2=1 mod 2047 (is a square root of 1, so its order is 2). So you could find the factors even if your B1 and B2 are both 2.

This was a not so fortunate example. P-1 tries to find the order of 3 (or any x) in m (the number you try to factor). If this m is prime, then Fermat's theorem says that xp-1=1 mod m. It means that the order of x can be any divisor (prime or not prime factor) of p-1. For example, the order of 3 in 11 is 5 (a divisor of 11-1, as 11 is prime, 35=1 mod 11). When you multiply two primes, m=p*q, then the order of x in m will be the lcm of the orders of x in p and q. It means that lcm(q-1, p-1) will always be a multiple of the order you look for. P-1 tries to find this order by taking all numbers below B1, making the LCM of their product, and raising x (in our case 3) at that number (multiplied by 2p for mersenne). If the order of 3 is there, then you have a power of 3 which is 1 mod m (because you rose 3 at a multiple of its order), and you go back on the chain to find exactly how much the order is, and extract the factor, no matter if the factor is much bigger. This generally speaking, and without any optimization.

Last fiddled with by LaurV on 2011-10-06 at 14:01
LaurV is offline   Reply With Quote