mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Combinatorics & Combinatorial Number Theory

Reply
 
Thread Tools
Old 2020-08-14, 21:44   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

52·11 Posts
Default is the factorisation of Mp-1 an advantage ?

A peaceful and pleasant night for you,


if I know the factorisation or a part of the factorisation of Mp-1
do I have any advantages for checking the primality ?


(Mp should be a Mersenne number)


Or in other words, is the factorisation of p-1 helpful ?



I know the theorem of Pocklington for proofing primality
https://en.wikipedia.org/wiki/Pockli...primality_test


Thanks in advance if you spend me some lines

Bernhard
bhelmes is online now   Reply With Quote
Old 2020-08-14, 22:05   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

17·83 Posts
Default

Quote:
Originally Posted by bhelmes View Post
if I know the factorisation or a part of the factorisation of Mp-1
do I have any advantages for checking the primality ?
Probably there is no advantage for that, but any odd factor of Mp-1 could give a non-trival factor of another Mersenne number (with prime index),
since r|Mp-1=2*(2^(p-1)-1).

Last fiddled with by R. Gerbicz on 2020-08-14 at 22:07
R. Gerbicz is offline   Reply With Quote
Old 2020-08-14, 22:13   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23A816 Posts
Default

Quote:
Originally Posted by bhelmes View Post
Or in other words, is the factorisation of Mp-1 helpful ?
N=Mp are a beautiful example of being proven with >>33.33% N+1 factorization (indeed, 100%).
Factorization of N-1 is needless, when you have a 100% N+1 factorization.
Batalov is offline   Reply With Quote
Old 2020-08-16, 10:34   #4
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

25×5 Posts
Default

Agree with Batalov; for proving primality of M_p, since the full factorization of M_p + 1 is trivial, we do not gain anything from the factorization of M_p - 1.

Of course, it may be fun to find the factorization anyway; here is a factordb query for tiny examples.

/JeppeSN
JeppeSN is online now   Reply With Quote
Old 2020-08-16, 11:51   #5
axn
 
axn's Avatar
 
Jun 2003

5×23×41 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
Of course, it may be fun to find the factorization anyway; here is a factordb query for tiny examples.
You linked to Mp-2.
axn is offline   Reply With Quote
Old 2020-08-17, 20:49   #6
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

25×5 Posts
Red face

Quote:
Originally Posted by axn View Post
You linked to Mp-2.
Oops, that is right. It should have been 2^n-2 for n prime, or 2*(2^(n-1) - 1). /JeppeSN
JeppeSN is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factorisation for p-1, p is prime bhelmes Miscellaneous Math 31 2020-10-09 08:22
factorisation devarajkandadai Factoring 7 2013-07-06 03:44
Records for complete factorisation Brian-E Math 25 2009-12-16 21:40
Being coy about a factorisation fivemack Math 7 2007-11-17 01:27
Kraitchik's factorisation method Robertcop Math 2 2006-02-06 21:03

All times are UTC. The time now is 21:02.

Tue Oct 27 21:02:27 UTC 2020 up 47 days, 18:13, 2 users, load averages: 1.94, 2.04, 2.04

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.