I already know I'm a kook, but humor me.

[jasong]

I know there are about 200 morons before me that have come up with a similar idea, but I can't get the notion out of my head that there's some sort of algebraic pattern between k*2^n-1 and k*2^(n+1)-1.

If someone could explain Lucas-Lehmer testing, starting with 2^n-1 and extending it to k*2^n-1, I'd appreciate it. Btw, I don't understand a lot of the symbols involved which is what my search got me.

I know I'm a moron, but I want to make sure, lol.

[R.D. Silverman]

Originally Posted by jasong

I know there are about 200 morons before me that have come up with a similar idea, but I can't get the notion out of my head that there's some sort of algebraic pattern between k*2^n-1 and k*2^(n+1)-1.

If someone could explain Lucas-Lehmer testing, starting with 2^n-1 and extending it to k*2^n-1, I'd appreciate it. Btw, I don't understand a lot of the symbols involved which is what my search got me.

I know I'm a moron, but I want to make sure, lol.

Of course there is an algebraic pattern between x = k*2^n-1 and
y = k*2^(n+1) - 1; y = 2x-1. What's the big deal???

I explained LL testing once and got flamed for it. I am not going to explain
it again.

[ewmayer]

Originally Posted by R.D. Silverman

Of course there is an algebraic pattern between x = k*2^n-1 and y = k*2^(n+1) - 1; y = 2x-1. What's the big deal???

I'm pretty sure Bob meant to say "y = 2x + 1."

You may want to peruse the Mathworld page on Sophie Germain primes.

[jasong]

Originally Posted by ewmayer

I'm pretty sure Bob meant to say "y = 2x + 1."

You may want to peruse the Mathworld page on Sophie Germain primes.

Actually, the half-baked idea I was referring to involves shortening the LLR process, although y=2x+1 is definitely interesting.

Whether Mr. Silverman was flamed or not, I'd appreciate a link.

Thanks

[jasong]

Originally Posted by jasong

Actually, the half-baked idea I was referring to involves shortening the LLR process, although y=2x+1 is definitely interesting.

Whether Mr. Silverman was flamed or not, I'd appreciate a link.

Thanks

Okay, obviously people either don't know, aren't interested in telling me, or the topic's taken such a bad turn that the people who could educate me on the process simply think this is a flame thread.

Basically, and this is actually an expansion on my original interest, I was wondering if anyone who understands Lucas-Lehmer testing has ever sat down with a computer and attempted to find subpatterns in the modular arithmetic(perhaps another version of a probable prime test). Even if a subpattern could only get rid of, say, 3% of tests, that would be a major breakthrough. Alternately, someone might be able to come up with a test which shortens the amount of time to find a prime, but it's not necessarily the smallest for that kn pair.(Might make Riesel or Sierpenski project review their main goals).

I'm certainly not the smartest man in the room. While my math IQ is(or was) 130 in the 9th grade, most of my 11th and 12th grade years were spent in a mental hospital. At age 31, I'm intending to go back to college in January, where I intend to expand my rudely interrupted education.

To go back to my original question: Has anyone ever sat down with a computer and attempted to find subpatterns in the numbers that could be helpful?

Edit: Being very uneducated in modular arithmetic I ask the following question: Would it be possible to make some sort of shortcut in the math, where a new version of a probable prime test might take, say, 10% of the time, but remove, say, 30% of the tests?(the % numbers are random btw)

[Numbers]

As you claim no expertise in math there is no point in going into too much detail, so this can be considered the 5-minute introduction to L/L testing.

In 1878 the French mathematician Edouard Lucas proved that a number n = 1(mod 4) of the form 2^p –1 will be prime if and only if it divides into a second number of the form L_n = x^{2^{n-1}} + y^{2^{n-1}} where x = 2 + sqrt{3} and y = 2 - sqrt{3).

In 1930, the American mathematician Derrick Lucas proved that this did not only apply when n = 1(mod 4) but to all odd primes. The test is therefore named after the two people who independently developed and proved it, even though they never met.

Basically, the test performed by Prime95 is just a massive long division to see whether the number being tested divides into the appropriate Lucas-Lehmer number. Therefore the test is not finding factors of the number being tested and no useful results are possible until the test has completed. For this reason I would think that “shortening” the test is not an option.

For a longer, but no more technical explanation you could usefully try Marcus du Sautoy’s book “The Music of the Primes”, or maybe you could even search this site as I am sure many better qualified people than I have explained this here before.

Note: n = 1(mod 4) means will have a remainder of 1 after dividing by 4.

[jasong]

Originally Posted by Numbers

As you claim no expertise in math there is no point in going into too much detail, so this can be considered the 5-minute introduction to L/L testing.

In 1878 the French mathematician Edouard Lucas proved that a number n = 1(mod 4) of the form 2^p –1 will be prime if and only if it divides into a second number of the form L_n = x^{2^{n-1}} + y^{2^{n-1}} where x = 2 + sqrt{3} and y = 2 - sqrt{3).

In 1930, the American mathematician Derrick Lucas proved that this did not only apply when n = 1(mod 4) but to all odd primes. The test is therefore named after the two people who independently developed and proved it, even though they never met.

Basically, the test performed by Prime95 is just a massive long division to see whether the number being tested divides into the appropriate Lucas-Lehmer number. Therefore the test is not finding factors of the number being tested and no useful results are possible until the test has completed. For this reason I would think that “shortening” the test is not an option.

For a longer, but no more technical explanation you could usefully try Marcus du Sautoy’s book “The Music of the Primes”, or maybe you could even search this site as I am sure many better qualified people than I have explained this here before.

Note: n = 1(mod 4) means will have a remainder of 1 after dividing by 4.

Thanks Numbers. The meaning of some of the notation eludes me. Since this forum is inappropriate for the amount of learning probably required of me, I'll quit asking questions, although the idea of a shortcut is something I still want to explore. After some hardcore studying, of course.

[Numbers]

Originally Posted by jasong

... I'll quit asking questions, although the idea of a shortcut is something I still want to explore.

There is no need for you to quit asking questions; the only really stupid question is the one that goes unasked. But it might be worth remembering that many of the people who visit this forum either are or were professional mathematicians, university professors and the like – I am not in this league. Many of them have been working in this particular field of maths for ten, or twenty years or more, and the success of this project is a testament to their expertise, dedication and professionalism. So asking them whether they have ever sat down and looked at the patterns in the numbers is a bit like asking a baker whether he ever put his hand in a bag of flour. It’s what they do and have been doing for a long time. So when people who are, by their own admission, ignorant of the subject come along and suggest that they might have been doing it wrong all this time, is it really all that surprising that they do not receive a friendly response?

[R.D. Silverman]

Originally Posted by Numbers

So asking them whether they have ever sat down and looked at the patterns in the numbers is a bit like asking a baker whether he ever put his hand in a bag of flour. It’s what they do and have been doing for a long time. So when people who are, by their own admission, ignorant of the subject come along and suggest that they might have been doing it wrong all this time, is it really all that surprising that they do not receive a friendly response?

Earlier quote:

"Being very uneducated in modular arithmetic"

Friendly Response?

When someone who can't even be bothered to learn the basic notation
of the subject they are trying to discuss comes along and starts making
suggestions about "looking for patterns", it is sheer arrogance.


Ignorance is curable. But someone who will *not* cure his/her ignorance
by acquiring the necessary background to discuss a subject is a *crank*

I too was very ignorant of this subject at what time. However, because I
was interested I went out and grabbed every number theory book I could
find and *read* them. And *worked the exercizes*. I have zero
tolerance (and nothing but contempt) for newcomers who refuse to
acquire the background to discuss a subject (*any* subject, not just math)
in which they claim interest.

And some questions ARE stupid. Stupid questions are those for which the
poser can't possibly understand any response, because by their own
admission, they are *totally* ignorant of the subject. Asking questions
is legitimate *if and only if you have done your homework". As any teacher
will tell you. Teachers have no patience (nor should they) for those who
will not do their homework.

And experts *have* looked at trying to improve the L-L test. However,
most wannabees fail to understand how *very efficient* the test already
is. To test N = 2^p-1, it requires log(N) multiplications mod N.
So when totally ignorant newcomers along blathering about improving the
test, it is sheerest arrogance. It would be like my attempting to suggest
"improvements" to experts in (say) Quantum Gauge Field Theory. I can
understand the math, but am totally lacking in the necessary background.

People should cure their ignorance. Then they can start making suggestions.

[trilliwig]

Originally Posted by jasong

Whether Mr. Silverman was flamed or not, I'd appreciate a link.

http://www.mersenneforum.org/showpos...01&postcount=2

To understand it though, you'll need to know what a group and subgroup are, what we mean by the order of an element of the group and what it implies, what a primitive root is (in this context, an element of maximal order), and what notation like GF means. Happy learning.

[cheesehead]

Originally Posted by jasong

I was wondering if anyone who understands Lucas-Lehmer testing has ever sat down with a computer and attempted to find subpatterns in the modular arithmetic(perhaps another version of a probable prime test). Even if a subpattern could only get rid of, say, 3% of tests, that would be a major breakthrough.

Actually, the Lucas-Lehmer method doesn't require the use of modular arithmetic; it can be explained and used with only regular arithmetic ... for very small exponents.

However, it turns out that the numbers get so big for all but the smallest exponents that using modular arithmetic is a shortcut that becomes necessary in the practical sense (even though not ideally necessary). The biggest shortcut that could ever be made in the L-L method is the use of modular arithmetic.

What's hard to appreciate is that all the L_n numbers are constant. They don't change from one exponent to the next. The reason we have to re-compute them each time is that they are so large that it would be impossible to store the values of L_n once n gets past, say, 100. And computing them with modular arithmetic does make them different for each exponent, so they have to be re-computed each time.

Please see my May 28, 2003 explanation in the thread "Faster way to do LLT?" at http://www.mersenneforum.org/showthread.php?t=601