mersenneforum.org  

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

Reply
 
Thread Tools
Old 2005-12-10, 15:18   #34
ppo
 
ppo's Avatar
 
Aug 2004
italy

113 Posts
Default

Quote:
Originally Posted by MS63
One should NEVER ask a question unless one already knows the answer.

Seems to make this forum entirely pointless.
No, it is not like that. IFF you suspect that I am willfully lazy for not doing a little bit of work, you are authorized to jump on me. IF NOT, you have the choice to ignore my question or to try helping me.
That is how this forum should work, and I have seen many examples of that in previous posts, even from Bob Silverman.

Last fiddled with by ppo on 2005-12-10 at 15:20
ppo is offline   Reply With Quote
Old 2005-12-10, 16:54   #35
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×1,733 Posts
Default

Quote:
Originally Posted by MS63
Oh simple, foolish one.

One would have thought that a forum such as this was exactly the place to ask ANY questions and be provided with a RELEVANT answer, but no: According to 'Lord Bob' 1) is not permitted, 2) is mandatory, 3) is tantamount to a criminal offence, 4) is outlawed, and all are reasons to NOT ask one's question. One should NEVER ask a question unless one already knows the answer.

Seems to make this forum entirely pointless.
Ignorance is curable. Even Bob, especially Bob, is clear about that. He is just as ignorant as anyone on some subjects, and freely admits it. The difference between him and some people is that he very rarely, if ever, makes pronouncements on subjects where he knows he is ignorant. He asks questions in an attempt to learn and he performs background reading so he knows how to ask sensible questions.

Ask Bob a sensible question and he will give a sensible answer. I suggest that you read through his responses to people who have asked sensible questions earlier.

And yes, I do mean "sensible" and not "advanced". He has answered questions before now that required only very simple mathematical concepts to answer.

Asking stupid questions, on the other hand, is guaranteed to annoy Bob (and irritate many other people, for that matter). Being able to distinguish between sensible and stupid questions becomes much easier if you've done your homework.


Paul
xilman is offline   Reply With Quote
Old 2005-12-11, 02:52   #36
drew
 
drew's Avatar
 
Jun 2005

2×191 Posts
Default

Quote:
Originally Posted by ppo
I understand that the all exercise is pointless, but I am curious, and this is probably my opportunity to be jumped on by Bob, or by all of you, for
1) being ignorant
2) not having done my homework
3) being lazy
4) asking stupid questions
but I am still unable to work backward starting from 0.
Would some kind soul walk me through an example with a very small exponent?
Hey PPO,

Don't let Bob get to you. Hopefully someday he'll recognize that there's more value to a person than how little they know about his particular field of interest, and develop some people skills.

Let's use the previously quoted example of 2^7-1, which is 127.

To do the forward test, start out with S0=4. Each successive iteration is the square of the previous minus 2, mod 127.

S1 = S0*S0-2 = 4*4-2 = 14
S2 = 14*14 - 2 = 194 = 67 mod 127

Since we're interested only in modulus 127, which is the remainder of a division by 127, we get 67 (194/127 = 1 remainder 67)

S3 = 67*67 - 2 = 4487 = 42 mod 127
S4 = 42*42 - 2 = 1762 = 111 mod 127
S5 = 111*111 - 2 = 12319 = 0 mod 127

When we get to 5, which is n-2, we stop. If it's zero, then the number is prime. Yipee!

Now, assuming we start by assuming S5 = 0, how can we work backwards to get S4? Well, we solve for S4:

S5 = S4^2 - 2
S4 = sqrt(S5 + 2) = sqrt(2)

We need to know the square root of 2 using the mod 127 field. In this field, 2 can have any of the following values:

2
127+2=129
127*2+2=256
127*3+2=383
127*4+2=510
.
.
.
127*125+2 = 15877

So there are many values which can be possible square roots. We're only interested in the above values that are perfect squares, since our number field contains only integers. In the set defined above, the values 256 and 12319 are both perfect squares of 16 and 111. I created a spreadsheet to work that out, and the computation for this is much more involved than the squaring and subtracting used for the forward step.

What's more is that you end up with two answers! The backward step is not deterministic. You need to consider both of these possibilities as being potential S4 values, which leaves exponentially more possibile values as you go a given number of steps backward.

The simple fact is that by the time you perform even 1 backwards iteration, you could solve the entire problem using the forward steps. Heck, with numbers as large as we're testing, I don't think the universe is old enough to have perform one iteration. We'd need to evaluate over 2^10000000 square roots.

Drew

Last fiddled with by drew on 2005-12-11 at 03:07
drew is offline   Reply With Quote
Old 2005-12-11, 09:12   #37
ppo
 
ppo's Avatar
 
Aug 2004
italy

11100012 Posts
Default

Quote:
Originally Posted by drew

Don't let Bob get to you.
Thanks for yours detailed and helpful answer, very good.
By the way I think that Bob is only jumping on people when he has some evidence that they are not doing at least some effort to think to the problem before posting..and I WAS indeed lazy, so please everyone jump hard on me...
(PPO, write one hundrede times, I was lazy, I was lazy, I was... )
Let me explain: Being lazy as I am, tonight I decided to work on an example starting from the smallest exponent: 3, and working backward, I reached
immediately an S0 value of 3, not 4, so I suddenly realized that, let aside computational difficulties, there is a more compelling reason why the
meet somewere in between method cannot work: since there are different starting values for the LL sequence, all leading to an ending value of 0 for a Mersenne prime, there is an high probability that the forward and the backward methods will never meet. That should have been evident to me days ago, but , as I admit, I was too lazy to think...
ppo is offline   Reply With Quote
Old 2005-12-11, 14:24   #38
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·457 Posts
Default

Quote:
Originally Posted by ppo
... since there are different starting values for the LL sequence ...
This is well known since a long time. But I do not know of a nice paper describing and proving it.
The paper of Vasiga/Shallit (see: LLT DiGraph in Mersenne wiki for details and links) gives information about the tree and the loops, but not about the starting values.
Who can add something about these "starting values" in the wiki ?
Tony
T.Rex is offline   Reply With Quote
Old 2005-12-15, 05:39   #39
maxal
 
maxal's Avatar
 
Feb 2005

FC16 Posts
Default starting values

See sequence A018844 in OEIS.
maxal is offline   Reply With Quote
Old 2005-12-15, 09:06   #40
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·457 Posts
Default

Quote:
Originally Posted by maxal
See sequence A018844 in OEIS.
Thanks. I did not think to look there. But it does not really help, since the link "Herb Savage et al., Re: Mersenne: starting values for LL-test" is broken and there is no link to a paper providing a proof. Also, there is not a word about the fact that this Sequence of starting values can be built by: x_{i+1}=x_i(x_i^2-3) \ \pmod{M_q}.
And MathWorld does not say a word about these starting values. The same in "The Little Book of Bigger Primes" of Ribenboim.

Could someone (with better Number Theory skills than me) could propose MathWorld to add information about these starting values ? with links to papers and proofs !

Tony
T.Rex is offline   Reply With Quote
Old 2005-12-15, 09:23   #41
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by T.Rex
the link "Herb Savage et al., Re: Mersenne: starting values for LL-test" is broken
It was archived here.
maxal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SIGSEGV in xi3eK8 running torture test GordonWade Information & Answers 10 2018-02-18 00:07
Can I just start Prime95 by running torture test? marks9GIMPS Information & Answers 5 2011-06-05 18:44
Dual Core and running the same test..? Unregistered Information & Answers 1 2008-03-01 15:02
Prime95 crashing while running blend test day61 Hardware 1 2007-01-30 12:03
Running a LL test on 2 different machines lycorn Software 10 2003-01-13 19:34

All times are UTC. The time now is 08:16.

Fri Dec 4 08:16:13 UTC 2020 up 1 day, 4:27, 0 users, load averages: 1.21, 1.31, 1.33

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.