Doubt about P-1 algorithm

[alpertron]

In the example given in the Wiki, only step 1 is done. Note that according to the last paragraph of the "Step 1" section, the exponent of the Mersenne number will divide p-1, so that exponent is included as well when computing the value E, so step 2 is not needed in this case.

[LaurV]

Originally Posted by R.D. Silverman

This is false. <snip>
This is JUST A COINCIDENCE and can not be relied upon.

This is not false, and it is not a coincidence. I may not understand number field sieve algorithm, but the basic algorithms I understand by heart, I can prove everything, and also I did different implementation for them with small numbers to check if I understood, at the time when I was learning about them. This is up to (and including) quadratic sieve.

All this basic algorithms (including P-1) are very easy to understand assuming one knows basic algebra and Fermat's little theorem (FT). You do not need anything else (I do not mean you personally, I mean in general, and I am convinced that you personally know these facts much better than me and than anyone here!) .

Basic algebra tells us that any poly of the form can be decomposed into and FT tells us that for any prime p and any a coprime with p we have (I pick the form most convenient here) mod p.

So the order of any x in any prime p is a factor of p-1. If you multiply two p's together to get n, then the order of x in n is LCM of the two orders, that turns out to be a factor of LCM(p₁-1, p₂-1). Now, for a mersenne number m, all factors are 2*k*p+1, so the order of any x in m is a factor of LCM(2*k_i*p, for all i). This order is what P-1 tries to find, taking x=3. This number may contain p, or it may not, if you like (what really happens can be seen, considering the fact that all factors of m are either 8k+1 or 8k-1, and the 8k-1 factors exist always, and they are in an odd number, this is a simple exercise) but this is not important now.

If m has a factor q, P-1 will find this factor if q-1 is B-smooth. Due to the form of the factors, you can place p in the product from the beginning (in fact you can place 2*p there, because if you get 3^(2*P*E)=1, you go back step by step - see the "basic algebra" reference above) and this is how you reduce the problem from "q-1 being B-smooth" to "k being B-smooth".

From this link: "This method when adapted to Mersenne numbers is even more effective. Remember, that the factor q is of the form 2kp+1. It is easy to modify the P-1 method such that it will find the factor q whenever k is highly composite."

This is how you "modify" it.

That is, in fact, what I intended to say in the previous post. I can detail it (at the "entry level") if some beginner is interested. I am not intending to teach you math. You may consider the fact that for many of us, your math language is too advanced. So, let us talk our language.

[LaurV]

Originally Posted by alpertron

In the example given in the Wiki, only step 1 is done. Note that according to the last paragraph of the "Step 1" section, the exponent of the Mersenne number will divide p-1, so that exponent is included as well when computing the value E, so step 2 is not needed in this case.

This formulation is a bit ambiguous, the exponent is p, that does not divide p-1.

[Dubslow]

I would be interested in less advanced vocabulary. As has been discussed elsewhere, I've never studied and sort of number theory in any depth at all, and I have no idea what "order" means, and after that is where I get seriously lost. (Also, if p is prime, wouldn't any integer a be coprime to p?)

[axn]

Originally Posted by Dubslow

I would be interested in less advanced vocabulary. As has been discussed elsewhere, I've never studied and sort of number theory in any depth at all, and I have no idea what "order" means, and after that is where I get seriously lost.

http://en.wikipedia.org/wiki/Order_%28group_theory%29 -- Best not to tackle it at this point, though.
Anyways, to understand P-1 algo, you don't need to know about orders and stuff.

Originally Posted by Dubslow

(Also, if p is prime, wouldn't any integer a be coprime to p?)

p, 2p, 3p, 4p, ...

[Mr. P-1]

Originally Posted by Dubslow

I would be interested in less advanced vocabulary. As has been discussed elsewhere, I've never studied and sort of number theory in any depth at all, and I have no idea what "order" means, and after that is where I get seriously lost. (Also, if p is prime, wouldn't any integer a be coprime to p?)

Here's how the P-1 algorithm works, without reference to "group order", and with modular arithmetic rendered into ordinary arithmetic.

Let E be a composite number. Let p be a prime number such that p-1 divides E. Specifically let p-1 = E/b for some integer b. Let a be an integer coprime to p.

Fermat's Little Theorem states that a^p-1 1 (mod p). This is equivalent to the statement that p divides a^p-1-1.

Elementary algebra tells us that a^E-1 = a^b(p-1)-1 is divisible by a^p-1-1.

Hence p divides a^E-1. It should be noted that, for values of E large enough to be useful, a^E-1 is an incalculably large number. What we can compute, without computing a^E-1, is a small number congruent to it modulo N, i.e., (a^E-1) - cN for some integer c. If p divides N, then p divides both terms, therefore divides their difference.

Therefore p divides GCD((a^E-1) - cN, N). This GCD may be N, in which case the algorithm has failed, otherwise it will be a (possibly composite) non-trivial proper factor of N.

I hit submit too soon. What I haven't covered in the above, is the appropriate choice of E.

[Mr. P-1]

Originally Posted by Mr. P-1

I hit submit too soon. What I haven't covered in the above, is the appropriate choice of E.

In the above, I made no assumptions about E other than that it was composite and it had at least one factor one less than a prime. In order to be useful, we need to choose E so that it has many factors each one less than a possible prime factor of N. (Other factors of E which do not satisfy this criterion are harmless.) If N is such that its factors have known divisibility properties, such as the 2kq+1 form of the factors of the Mersenne number Mq, then these divisors must be divisors of E in order for the algorithm to have a chance of finding any factors at all. So let E = E' * (known divisors of p-1). Imagine constructing E' by starting with 1 and successively multiplying in primes r_i, each chosen to give the maximum benefit to cost ratio available.

E₀ = 1
E_i = E_i-1 * r_i

Each new prime r_i increases the size of E' (hence of E) by log₂(r_i) bits. This is proportional to the increase in the cost of the computation.

The benefit of including r_i will be proportional to r_i^{-k[sub]i[/sub]}, where k_i is the multiplicity of r_i in E_i.

The benefit is therefore hugely sensitive to the choice of r_i, while the cost is relatively insensitive to that choice. To a first approximation, the best r_i will be the one that minimises r_i^{k[sub]i[/sub]}.

The end result will be that, for any i, the powers of each prime factor r of E_i will be as close as possible. The choice usually implemented, which is that given in the wiki, is to make E' equal to the product of all primes powers less than some B1. This is near optimal. We call the computation of a small number congruent to a^E-1 so chosen "stage 1".

Stage 2 involves computing a small number congruent to (a^{s[sub]1[/sub]*E}-1)(a^{s[sub]2[/sub]*E}-1)(a^{s[sub]2[/sub]*E}-1)... for recessive primes s_j between B1 and some B2. Each of the terms in the product substitutes s₂*E for E in the stage 1 computation and finds any prime factor p=k*(known divisors) + 1 if k is divisible by s₂ and k/s₂ is power-smooth to B1. Computing a small number congruent to any term in the product individually would be tantamount to choosing a non-optimal choice of E for stage 1, and would not be cost effective, but using the method described in the wiki, and other tricks and techniques not described there, small numbers congruent to successive terms in the product can be calculated quite cheaply.

[davieddy]

Originally Posted by axn

Remember that for mersennes, you're allowed a 'p' for free.

What! Not even a penny?

David

[Maximus]

Does P95 in stage 1 of p-1 factoring:
- calculate E=p1*p2*p3*...., then calculate a^E mod N;
- or calculate a1=a^p1 mod N, then a2=a1^p2 mod N, then a3=a2^p3 mod N, and so on;
- or another way?
p1, p2, p3, ... means powers of primes less then B1.
Who can tell, please?

[axn]

Originally Posted by Maximus

Does P95 in stage 1 of p-1 factoring:
- calculate E=p1*p2*p3*...., then calculate a^E mod N;
- or calculate a1=a^p1 mod N, then a2=a1^p2 mod N, then a3=a2^p3 mod N, and so on;
- or another way?
p1, p2, p3, ... means powers of primes less then B1.
Who can tell, please?

For the initial set of smaller primes, it uses the first method. Then switches over to the second method. You can look at the source yourselves.
http://www.mersenneforum.org/gimps/ (look in ecm.c)