2004-10-19, 16:56 | #1 |
Mar 2004
2^{2}×5^{3} Posts |
P-1 question of curiosity
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? |
2004-10-19, 17:46 | #2 |
"Nancy"
Aug 2002
Alexandria
2^{5}×7×11 Posts |
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 |
2004-10-19, 17:48 | #3 |
May 2004
2^{4}×5 Posts |
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 |
2004-10-20, 04:37 | #4 |
1CBE_{16} Posts |
Hi. Could you please Help?
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 Last fiddled with by Olympia on 2004-10-20 at 04:39 |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
A meaningless curiosity | fivemack | Aliquot Sequences | 2 | 2016-01-17 07:44 |
Results Curiosity | Gordon | PrimeNet | 1 | 2015-07-30 06:49 |
I see this as a bit of a mathematical curiosity... | petrw1 | Math | 4 | 2015-07-19 02:33 |
A Curiosity | R.D. Silverman | GMP-ECM | 4 | 2012-05-10 20:00 |
Curiosity | ET_ | Math | 7 | 2004-02-13 17:36 |