P-1 question of curiosity

[JuanTutors]

This is more a question of curiosity than anything else:

What happens if, say, EVERY prime factor of a specific composite Mersenne number was "very smooth" for P-1 testing? I.e. what if for some specific M_p, Prime95 sets the first bound B1, and it just so happens that every prime q dividing M_p is B1-smooth? Would the P-1 test detect that? Would it somehow fail to detect that? Would your computer blow up?

[akruppa]

Every prime factor of M_p would appear in the output, that means P-1 would simply report M_p itself as the factor found.

Alex

[dave_dm]

I don't know what Prime95 itself does but the p-1 algorithm can detect this, yes. Let the gcd at the end be d = gcd(a^X-1, n), where n is the number to be factored and X is the product of all prime powers < B1. When d=1 we fail to find a factor; when 1<d<n, we find a nontrivial factor.

You are talking about the case a^X=1 (mod p) for all p | n, i.e. a^X=1 (mod n), so this corresponds to d = n. If this happens, repeat the calculation with a lower B1 until you catch some but not all of the factors.

In practice, this situation won't arise unless you're trying to factor small numbers with a bad choice of B1.

The same principle applies to ecm.

Dave

Suppose that p>3 is an odd prime and that a is not equal to 1 mod p. Prove that if a^3 congruences 1 mod p, then p congruences 1 mod 3. Hint: what happens if you divide p-1 by 3? What does Fermat's little theorem says all about this?

Thank so much.

Olympia