mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-10-19, 16:56   #1
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

3·163 Posts
Default 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?
JuanTutors is offline   Reply With Quote
Old 2004-10-19, 17:46   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2004-10-19, 17:48   #3
dave_dm
 
May 2004

24×5 Posts
Default

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
dave_dm is offline   Reply With Quote
Old 2004-10-20, 04:37   #4
Olympia
 

13·431 Posts
Default 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
  Reply With Quote
Reply

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

All times are UTC. The time now is 05:07.

Tue Sep 29 05:07:05 UTC 2020 up 19 days, 2:18, 0 users, load averages: 1.63, 1.51, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.