Factors of a Mersenne number

From Rosetta Code
Task
Factors of a Mersenne number
You are encouraged to solve this task according to the task description, using any language you may know.

A Mersenne number is a number in the form of 2P-1.

If P is prime, the Mersenne number may be a Mersenne prime (if P is not prime, the Mersenne number is also not prime).

In the search for Mersenne prime numbers it is advantageous to eliminate exponents by finding a small factor before starting a, potentially lengthy, Lucas-Lehmer test.

There are very efficient algorithms for determining if a number divides 2P-1 (or equivalently, if 2P mod (the number) = 1). Some languages already have built-in implementations of this exponent-and-mod operation (called modPow or similar).

The following is how to implement this modPow yourself:

For example, let's compute 223 mod 47. Convert the exponent 23 to binary, you get 10111. Starting with square = 1, repeatedly square it. Remove the top bit of the exponent, and if it's 1 multiply square by the base of the exponentiation (2), then compute square modulo 47. Use the result of the modulo from the last step as the initial value of square in the next step:

                  remove       optional   
      square      top bit   multiply by 2   mod 47
   ────────────   ───────   ─────────────   ────── 
   1*1 = 1        1  0111   1*2 = 2            2
   2*2 = 4        0   111      no              4
   4*4 = 16       1    11   16*2 = 32         32
   32*32 = 1024   1     1   1024*2 = 2048     27
   27*27 = 729    1         729*2 = 1458       1

Since 223 mod 47 = 1, 47 is a factor of 2P-1. (To see this, subtract 1 from both sides: 223-1 = 0 mod 47.) Since we've shown that 47 is a factor, 223-1 is not prime. Further properties of Mersenne numbers allow us to refine the process even more. Any factor q of 2P-1 must be of the form 2kP+1, k being a positive integer or zero. Furthermore, q must be 1 or 7 mod 8. Finally any potential factor q must be prime. As in other trial division algorithms, the algorithm stops when 2kP+1 > sqrt(N).

These primality tests only work on Mersenne numbers where P is prime. For example, M4=15 yields no factors using these techniques, but factors into 3 and 5, neither of which fit 2kP+1.


Task

Using the above method find a factor of 2929-1 (aka M929)


Related tasks


See also



360 Assembly[edit]

Translation of: BBC BASIC

Use of bitwise operations (TM (Test under Mask), SLA (Shift Left Arithmetic),SRA (Shift Right Arithmetic)).

*        Factors of a Mersenne number  11/09/2015
MERSENNE CSECT
USING MERSENNE,R15
MVC Q,=F'929' q=929 (M929=2**929-1)
LA R6,1 k=1
LOOPK C R6,=F'1048576' do k=1 to 2**20
BNL ELOOPK
LR R5,R6 k
M R4,Q *q
SLA R5,1 *2 by shift left 1
LA R5,1(R5) +1
ST R5,P p=k*q*2+1
L R2,P p
N R2,=F'7' p&7
C R2,=F'1' if ((p&7)=1) p='*001'
BE OK
C R2,=F'7' or if ((p&7)=7) p='*111'
BNE NOTOK
OK MVI PRIME,X'00' then prime=false is prime?
LA R2,2 loop count=2
LA R1,2 j=2 and after j=3
J2J3 L R4,P p
SRDA R4,32 r4>>r5
DR R4,R1 p/j
LTR R4,R4 if p//j=0
BZ NOTPRIME then goto notprime
LA R1,1(R1) j=j+1
BCT R2,J2J3
LA R7,5 d=5
WHILED LR R5,R7 d
MR R4,R7 *d
C R5,P do while(d*d<=p)
BH EWHILED
LA R2,2 loop count=2
LA R1,2 j=2 and after j=4
J2J4 L R4,P p
SRDA R4,32 r4>>r5
DR R4,R7 /d
LTR R4,R4 if p//d=0
BZ NOTPRIME then goto notprime
AR R7,R1 d=d+j
LA R1,2(R1) j=j+2
BCT R2,J2J4
B WHILED
EWHILED MVI PRIME,X'01' prime=true so is prime
NOTPRIME L R8,Q i=q
MVC Y,=F'1' y=1
MVC Z,=F'2' z=2
WHILEI LTR R8,R8 do while(i^=0)
BZ EWHILEI
ST R8,PG i
TM PG+3,B'00000001' if first bit of i not 1
BZ NOTFIRST
L R5,Y y
M R4,Z *z
LA R4,0
D R4,P /p
ST R4,Y y=(y*z)//p
NOTFIRST L R5,Z z
M R4,Z *z
LA R4,0
D R4,P /p
ST R4,Z z=(z*z)//p
SRA R8,1 i=i/2 by shift right 1
B WHILEI
EWHILEI CLI PRIME,X'01' if prime
BNE NOTOK
CLC Y,=F'1' and if y=1
BNE NOTOK
MVC FACTOR,P then factor=p
B OKFACTOR
NOTOK LA R6,1(R6) k=k+1
B LOOPK
ELOOPK MVC FACTOR,=F'0' factor=0
OKFACTOR L R1,Q
XDECO R1,PG edit q
L R1,FACTOR
XDECO R1,PG+12 edit factor
XPRNT PG,24 print
XR R15,R15
BR R14
PRIME DS X flag for prime
Q DS F
P DS F
Y DS F
Z DS F
FACTOR DS F a factor of q
PG DS CL24 buffer
YREGS
END MERSENNE
Output:
         929       13007

Ada[edit]

mersenne.adb:

with Ada.Text_IO;
-- reuse Is_Prime from [[Primality by Trial Division]]
with Is_Prime;
 
procedure Mersenne is
function Is_Set (Number : Natural; Bit : Positive) return Boolean is
begin
return Number / 2 ** (Bit - 1) mod 2 = 1;
end Is_Set;
 
function Get_Max_Bit (Number : Natural) return Natural is
Test : Natural := 0;
begin
while 2 ** Test <= Number loop
Test := Test + 1;
end loop;
return Test;
end Get_Max_Bit;
 
function Modular_Power (Base, Exponent, Modulus : Positive) return Natural is
Maximum_Bit : constant Natural := Get_Max_Bit (Exponent);
Square  : Natural := 1;
begin
for Bit in reverse 1 .. Maximum_Bit loop
Square := Square ** 2;
if Is_Set (Exponent, Bit) then
Square := Square * Base;
end if;
Square := Square mod Modulus;
end loop;
return Square;
end Modular_Power;
 
Not_A_Prime_Exponent : exception;
 
function Get_Factor (Exponent : Positive) return Natural is
Factor : Positive;
begin
if not Is_Prime (Exponent) then
raise Not_A_Prime_Exponent;
end if;
for K in 1 .. 16384 / Exponent loop
Factor := 2 * K * Exponent + 1;
if Factor mod 8 = 1 or else Factor mod 8 = 7 then
if Is_Prime (Factor) and then Modular_Power (2, Exponent, Factor) = 1 then
return Factor;
end if;
end if;
end loop;
return 0;
end Get_Factor;
 
To_Test : constant Positive := 929;
Factor  : Natural;
begin
Ada.Text_IO.Put ("2 **" & Integer'Image (To_Test) & " - 1 ");
begin
Factor := Get_Factor (To_Test);
if Factor = 0 then
Ada.Text_IO.Put_Line ("is prime.");
else
Ada.Text_IO.Put_Line ("has factor" & Integer'Image (Factor));
end if;
exception
when Not_A_Prime_Exponent =>
Ada.Text_IO.Put_Line ("is not a Mersenne number");
end;
end Mersenne;
Output:
2 ** 929 - 1 has factor 13007

ALGOL 68[edit]

Translation of: Fortran
Works with: ALGOL 68 version Standard - with prelude inserted manually
Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386
MODE ISPRIMEINT = INT;
PR READ "prelude/is_prime.a68" PR;
 
MODE POWMODSTRUCT = INT;
PR READ "prelude/pow_mod.a68" PR;
 
PROC m factor = (INT p)INT:BEGIN
INT m factor;
INT max k, msb, n, q;
 
FOR i FROM bits width - 2 BY -1 TO 0 WHILE ( BIN p SHR i AND 2r1 ) = 2r0 DO
msb := i
OD;
 
max k := ENTIER sqrt(max int) OVER p; # limit for k to prevent overflow of max int #
FOR k FROM 1 TO max k DO
q := 2*p*k + 1;
IF NOT is prime(q) THEN
SKIP
ELIF q MOD 8 /= 1 AND q MOD 8 /= 7 THEN
SKIP
ELSE
n := pow mod(2,p,q);
IF n = 1 THEN
m factor := q;
return
FI
FI
OD;
m factor := 0;
return:
m factor
END;
 
BEGIN
 
INT exponent, factor;
print("Enter exponent of Mersenne number:");
read(exponent);
IF NOT is prime(exponent) THEN
print(("Exponent is not prime: ", exponent, new line))
ELSE
factor := m factor(exponent);
IF factor = 0 THEN
print(("No factor found for M", exponent, new line))
ELSE
print(("M", exponent, " has a factor: ", factor, new line))
FI
FI
 
END

Example:

Enter exponent of Mersenne number:929
M       +929 has a factor:      +13007

AutoHotkey[edit]

ahk discussion

MsgBox % MFact(27)  ;-1: 27 is not prime
MsgBox % MFact(2) ; 0
MsgBox % MFact(3) ; 0
MsgBox % MFact(5) ; 0
MsgBox % MFact(7) ; 0
MsgBox % MFact(11) ; 23
MsgBox % MFact(13) ; 0
MsgBox % MFact(17) ; 0
MsgBox % MFact(19) ; 0
MsgBox % MFact(23) ; 47
MsgBox % MFact(29) ; 233
MsgBox % MFact(31) ; 0
MsgBox % MFact(37) ; 223
MsgBox % MFact(41) ; 13367
MsgBox % MFact(43) ; 431
MsgBox % MFact(47) ; 2351
MsgBox % MFact(53) ; 6361
MsgBox % MFact(929) ; 13007
 
MFact(p) { ; blank if 2**p-1 can be prime, otherwise a prime divisor < 2**32
If !IsPrime32(p)
Return -1 ; Error (p must be prime)
Loop % 2.0**(p<64 ? p/2-1 : 31)/p ; test prime divisors < 2**32, up to sqrt(2**p-1)
If (((q:=2*p*A_Index+1)&7 = 1 || q&7 = 7) && IsPrime32(q) && PowMod(2,p,q)=1)
Return q
Return 0
}
 
IsPrime32(n) { ; n < 2**32
If n in 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
Return 1
If (!(n&1)||!mod(n,3)||!mod(n,5)||!mod(n,7)||!mod(n,11)||!mod(n,13)||!mod(n,17)||!mod(n,19))
Return 0
n1 := d := n-1, s := 0
While !(d&1)
d>>=1, s++
Loop 3 {
x := PowMod( A_Index=1 ? 2 : A_Index=2 ? 7 : 61, d, n)
If (x=1 || x=n1)
Continue
Loop % s-1
If (1 = x:=PowMod(x,2,n))
Return 0
Else If (x = n1)
Break
IfLess x,%n1%, Return 0
}
Return 1
}
 
PowMod(x,n,m) { ; x**n mod m
y := 1, i := n, z := x
While i>0
y := i&1 ? mod(y*z,m) : y, z := mod(z*z,m), i >>= 1
Return y
}

BBC BASIC[edit]

      PRINT "A factor of M929 is "; FNmersenne_factor(929)
PRINT "A factor of M937 is "; FNmersenne_factor(937)
END
 
DEF FNmersenne_factor(P%)
LOCAL K%, Q%
IF NOT FNisprime(P%) THEN = -1
FOR K% = 1 TO 1000000
Q% = 2*K%*P% + 1
IF (Q% AND 7) = 1 OR (Q% AND 7) = 7 THEN
IF FNisprime(Q%) IF FNmodpow(2, P%, Q%) = 1 THEN = Q%
ENDIF
NEXT K%
= 0
 
DEF FNisprime(N%)
LOCAL D%
IF N% MOD 2=0 THEN = (N% = 2)
IF N% MOD 3=0 THEN = (N% = 3)
D% = 5
WHILE D% * D% <= N%
IF N% MOD D% = 0 THEN = FALSE
D% += 2
IF N% MOD D% = 0 THEN = FALSE
D% += 4
ENDWHILE
= TRUE
 
DEF FNmodpow(X%, N%, M%)
LOCAL I%, Y%, Z%
I% = N% : Y% = 1 : Z% = X%
WHILE I%
IF I% AND 1 THEN Y% = (Y% * Z%) MOD M%
Z% = (Z% * Z%) MOD M%
I% = I% >>> 1
ENDWHILE
= Y%
 
Output:
A factor of M929 is 13007
A factor of M937 is 28111

Bracmat[edit]

( ( modPow
= square P divisor highbit log 2pow
.  !arg:(?P.?divisor)
& 1:?square
& 2\L!P:#%?log+?
& 2^!log:?2pow
& whl
' ( mod
$ ( ( div$(!P.!2pow):1&2
| 1
)
* !square^2
. !divisor
)
 : ?square
& mod$(!P.!2pow):?P
& 1/2*!2pow:~/:?2pow
)
& !square
)
& ( isPrime
= incs nextincs primeCandidate nextPrimeCandidate quotient
. 1 1 2 2 (4 2 4 2 4 6 2 6:?incs)
 : ?nextincs
& 1:?primeCandidate
& ( nextPrimeCandidate
= ( !nextincs:&!incs:?nextincs
|
)
& !nextincs:%?inc ?nextincs
& !inc+!primeCandidate:?primeCandidate
)
& whl
' ( (!nextPrimeCandidate:?divisor)^2:~>!arg
& !arg*!divisor^-1:?quotient:/
)
& !quotient:/
)
& ( Factors-of-a-Mersenne-Number
= P k candidate bignum
.  !arg:?P
& 2^!P+-1:?bignum
& 0:?k
& whl
' ( 2*(1+!k:?k)*!P+1:?candidate
& !candidate^2:~>!bignum
& ( ~(mod$(!candidate.8):(1|7))
| ~(isPrime$!candidate)
| modPow$(!P.!candidate):?mp:~1
)
)
& !mp:1
& (!candidate.(2^!P+-1)*!candidate^-1)
)
& ( Factors-of-a-Mersenne-Number$929:(?divisorA.?divisorB)
& out
$ ( str
$ ("found some divisors of 2^" !P "-1 : " !divisorA " and " !divisorB)
)
| out$"no divisors found"
)
);
Output:
found some divisors of 2^!P-1 : 13007 and 348890248924938259750454781163390930305120269538278042934009621348894657205785
201247454118966026150852149399410259938217062100192168747352450719561908445272675574320888385228421992652298715687625495
638077382028762529439880103124705348782610789919949159935587158612289264184273

C[edit]

int isPrime(int n){
if (n%2==0) return n==2;
if (n%3==0) return n==3;
int d=5;
while(d*d<=n){
if(n%d==0) return 0;
d+=2;
if(n%d==0) return 0;
d+=4;}
return 1;}
 
main() {int i,d,p,r,q=929;
if (!isPrime(q)) return 1;
r=q;
while(r>0) r<<=1;
d=2*q+1;
do { for(p=r, i= 1; p; p<<= 1){
i=((long long)i * i) % d;
if (p < 0) i *= 2;
if (i > d) i -= d;}
if (i != 1) d += 2*q;
else break;
} while(1);
printf("2^%d - 1 = 0 (mod %d)\n", q, d);}

C#[edit]

using System;
 
namespace prog
{
class MainClass
{
public static void Main (string[] args)
{
int q = 929;
if ( !isPrime(q) ) return;
int r = q;
while( r > 0 )
r <<= 1;
int d = 2 * q + 1;
do
{
int i = 1;
for( int p=r; p!=0; p<<=1 )
{
i = (i*i) % d;
if (p < 0) i *= 2;
if (i > d) i -= d;
}
if (i != 1) d += 2 * q; else break;
}
while(true);
 
Console.WriteLine("2^"+q+"-1 = 0 (mod "+d+")");
}
 
static bool isPrime(int n)
{
if ( n % 2 == 0 ) return n == 2;
if ( n % 3 == 0 ) return n == 3;
int d = 5;
while( d*d <= n )
{
if ( n % d == 0 ) return false;
d += 2;
if ( n % d == 0 ) return false;
d += 4;
}
return true;
}
}
}

Clojure[edit]

Translation of: Python
(ns mersennenumber
(:gen-class))
 
(defn m* [p q m]
" Computes (p*q) mod m "
(mod (*' p q) m))
 
(defn power
"modular exponentiation (i.e. b^e mod m"
[b e m]
(loop [b b, e e, x 1]
(if (zero? e)
x
(if (even? e) (recur (m* b b m) (quot e 2) x)
(recur (m* b b m) (quot e 2) (m* b x m))))))
 
(defn divides? [k n]
" checks if k divides n "
(= (rem n k) 0))
 
(defn is-prime? [n]
" checks if n is prime "
(cond
(< n 2) false ; 0, 1 not prime (i.e. primes are greater than one)
(= n 2) true ; 2 is prime
(= 0 (mod n 2)) false ; all other evens are not prime
:else ; check for divisors up to sqrt(n)
(empty? (filter #(divides? % n) (take-while #(<= (* % %) n) (range 2 n))))))
 
;; Max k to check
(def MAX-K 16384)
 
(defn trial-factor [p k]
" check if k satisfies 2*k*P + 1 divides 2^p - 1 "
(let [q (+ (* 2 p k) 1)
mq (mod q 8)]
(cond
(not (is-prime? q)) nil
(and (not= 1 mq)
(not= 7 mq)) nil
(= 1 (power 2 p q)) q
:else nil)))
 
(defn m-factor [p]
" searches for k-factor "
(some #(trial-factor p %) (range 16384)))
 
(defn -main [p]
(if-not (is-prime? p)
(format "M%d = 2^%d - 1 exponent is not prime" p p)
(if-let [factor (m-factor p)]
(format "M%d = 2^%d - 1 is composite with factor %d" p p factor)
(format "M%d = 2^%d - 1 is prime" p p))))
 
;; Tests different p values
(doseq [p [2,3,4,5,7,11,13,17,19,23,29,31,37,41,43,47,53,929]
:let [s (-main p)]]
(println s))
 
Output:
M2 = 2^2 - 1 is prime
M3 = 2^3 - 1 is composite with factor 7
M4 = 2^4 - 1 exponent is not prime
M5 = 2^5 - 1 is composite with factor 31
M7 = 2^7 - 1 is composite with factor 127
M11 = 2^11 - 1 is composite with factor 23
M13 = 2^13 - 1 is composite with factor 8191
M17 = 2^17 - 1 is composite with factor 131071
M19 = 2^19 - 1 is composite with factor 524287
M23 = 2^23 - 1 is composite with factor 47
M29 = 2^29 - 1 is composite with factor 233
M31 = 2^31 - 1 is prime
M37 = 2^37 - 1 is composite with factor 223
M41 = 2^41 - 1 is composite with factor 13367
M43 = 2^43 - 1 is composite with factor 431
M47 = 2^47 - 1 is composite with factor 2351
M53 = 2^53 - 1 is composite with factor 6361
M929 = 2^929 - 1 is composite with factor 13007

CoffeeScript[edit]

Works with: node.js
Translation of: Ruby
mersenneFactor = (p) ->
limit = Math.sqrt(Math.pow(2,p) - 1)
k = 1
while (2*k*p - 1) < limit
q = 2*k*p + 1
if isPrime(q) and (q % 8 == 1 or q % 8 == 7) and trialFactor(2,p,q)