 mersenneforum.org > Math New LLT formula
 Register FAQ Search Today's Posts Mark Forums Read 2006-12-19, 16:58 #1 hoca   Dec 2006 3 Posts New LLT formula i use this formula to check primality of Mersenne numbers. S(0)=2 S(n)=2*S(n-1) - 1 and generalized form is : S(0)=2^(2-r) S(n)=(2^r)*S(n-1) - 2^(1-r)   2006-12-19, 21:12   #2
maxal

Feb 2005

26010 Posts Quote:
 Originally Posted by hoca i use this formula to check primality of Mersenne numbers. S(0)=2 S(n)=2*S(n-1) - 1
It can be easily shown by induction that S(n) = 2^n + 1.
How do you test primality of M_p using these numbers S(n)?

Last fiddled with by maxal on 2006-12-19 at 21:13   2006-12-20, 10:09 #3 hoca   Dec 2006 3 Posts opps sorry i forgot square of S(n-1) S(0)=2 S(n)=2*S(n-1)^2 - 1; and generalized form is : S(0)=2^(2-r) S(n)=(2^r)*S(n-1)^2 - 2^(1-r) forexample: S(0)=2 S(1)=2*2^2-1=7 =0 Mod(2^3-1) s(2)=2*7^2-1=97 s(3)=2*97^2-1=18817 =0 mod(2^5-1) and so on... OR s(n)=4*s(n-1)^2-1/2 s(0)=1 s(1)=4*1^2-1/2=7/2 =0 mod(7) s(2)=4*(7/2)^2-1/2=97/2 s(3)=4*(97/2)^2-1/2=18817/2=0 mod(31) .... pls any comment to proof or explain   2006-12-20, 14:40   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101010101002 Posts Quote:
 Originally Posted by hoca opps sorry i forgot square of S(n-1) S(0)=2 S(n)=2*S(n-1)^2 - 1;
Working mod M_p throughout:

This is just LL slightly disguised. Multiply by 2 giving:

2S(n) = 4S(n-1)^2 - 2 = [2 S(n-1)]^2 - 2

Compare the arithmetic for (say) M_5. In Your sequence we
get: 2,7,4,1,0, while the ordinary LL gives 4,14,8,2,0.

All you have done is divided the original sequence by 2. (or multiplied
by 2^-1 mod M_p)

Working (say) mod 127, LL gives 4,14,67,42,111,0 while
you sequence gives 2,7,97, ... etc.

Note that 97 = 67/2 mod 127 etc.   2006-12-20, 20:13 #5 Fusion_power   Aug 2003 Snicker, AL 26·3·5 Posts Translated into common terms, it means your method is not an improvement of the existing method. Its just a variant. Fusion   2006-12-21, 01:10   #6
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts Quote:
 Originally Posted by Fusion_power Translated into common terms, it means your method is not an improvement of the existing method. Its just a variant. Fusion

It isn't really a variant. It is simply multiplying the sequence by a
constant. (2^-1 mod N) It is also SLOWER.   2007-03-05, 17:36 #7 m_f_h   Feb 2007 24·33 Posts (*stumble in, some months late*) This sequence is also called A2812 on OEIS. It gives S(k) not only through the already mentioned relations, but also through the following great formula : ((c) by M_F_H !) For k>3, S(k) = 2 + 2^(2k) x 3 x product( A2812(i), i = 1..k-3 )^2 Unfortunately, this did not help me for my ultimate goal : calculate S(p-1) mod 2^p-1 as an explicit function of p and S(p-2) mod 2^(p-1)-1 ... Last fiddled with by m_f_h on 2007-03-05 at 17:47 Reason: removed title which consisted in ill-defined clipboard contents (copy-paste did not work directly into editing area...)   2007-03-05, 17:41   #8
ewmayer
2ω=0

Sep 2002
República de California

5×2,351 Posts Quote:
 Originally Posted by Fusion_power Translated into common terms, it means your method is not an improvement of the existing method. Its just a variant.
Which is about as good as can be expected from such an "ad hoca" approach...   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Software 1 2014-08-19 15:23 Uncwilly Lounge 29 2013-05-05 16:12 MattcAnderson Math 7 2013-01-14 23:29 Prime95 Data 18 2012-02-12 18:07 drake2 Math 10 2006-12-08 22:43

All times are UTC. The time now is 22:54.

Sun Jan 29 22:54:59 UTC 2023 up 164 days, 20:23, 0 users, load averages: 1.29, 0.99, 0.86