mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2003-06-08, 22:58   #1
daxm
 
Jun 2003

2 Posts
Default Need help with math problem re: searching for all primes.

About 10 years ago I created a mathematical algorythm that computes all the primes. I tested it against the first 2500 primes and it found them all (plus 2 or 3 non-primes). My program is slow to compute primes but I think that it could be sped up. I will do my best to describe it here (for those who wish to know more or have me explain something please email me at daxm@operamail.com).

Okay here goes:

To test if p is prime we run this program.
(First setup some initial varialbles)
d=p-1 (easier than computing p -1 all the time)
i=1 (a counter)
s=2 (This is our starting point)

if(s<>1)
s=(s*2)mod(d)
i=i+1
endif

When this is done then:

if(d/i) is a whole number then p is prime.

If there was only a quicker way to get to the d/i stage then we could zoom through all the primes. The problem is that i is a counter of how many times we goe through the loop.

Any suggestions? Comments?
daxm is offline   Reply With Quote
Old 2003-06-09, 07:44   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

1C1416 Posts
Default Re: Need help with math problem re: searching for all primes

Quote:
Originally Posted by daxm
To test if p is prime we run this program.
(First setup some initial varialbles)
d=p-1 (easier than computing p -1 all the time)
i=1 (a counter)
s=2 (This is our starting point)

if(s<>1)
s=(s*2)mod(d)
i=i+1
endif

When this is done then:

if(d/i) is a whole number then p is prime.
Let p = 9.
Then d = 9-1 = 8.

i = 1
s = 2

if(s<>1) is true, so we continue

s = (s*2)mod(d) = 2 * 2 mod 8 = 4
i= 1+1 = 2

After the endif, we have i = 2, s = 4, d = 8

d/i = 4 = a whole number, so p = 9 is ... ??prime??

Is your if/endif section supposed to be some sort of loop? E.g., a while/endwhile?
cheesehead is offline   Reply With Quote
Old 2003-06-11, 18:37   #3
flava
 
flava's Avatar
 
Feb 2003

2·59 Posts
Default

I think he ment a while not a if, and this might be a variant of Fermat's little theorem a^(p-1) = 1 mod p. It finds pseudoprimes.
flava is offline   Reply With Quote
Old 2003-06-13, 19:40   #4
daxm
 
Jun 2003

2 Posts
Default Re: Need help with math problem re: searching for all primes

Quote:
Originally Posted by cheesehead
Quote:
Originally Posted by daxm
To test if p is prime we run this program.
(First setup some initial varialbles)
d=p-1 (easier than computing p -1 all the time)
i=1 (a counter)
s=2 (This is our starting point)

if(s<>1)
s=(s*2)mod(d)
i=i+1
endif

When this is done then:

if(d/i) is a whole number then p is prime.
Let p = 9.
Then d = 9-1 = 8.

i = 1
s = 2

if(s<>1) is true, so we continue

s = (s*2)mod(d) = 2 * 2 mod 8 = 4
i= 1+1 = 2

After the endif, we have i = 2, s = 4, d = 8

d/i = 4 = a whole number, so p = 9 is ... ??prime??

Is your if/endif section supposed to be some sort of loop? E.g., a while/endwhile?

Oops, I did mean WHILE. It is a looping equation until s==1.
daxm is offline   Reply With Quote
Old 2003-06-13, 22:48   #5
S80780
 
Jan 2003
far from M40

12510 Posts
Default

How would you handle candidates of the form p=2^n + 1?
Except for n = 0 or some power of 2, they are all definitely composite.
If n is a power of 2, p might or might not be prime.
But your program would be unable to determine primality of any such number, as it would wind up in an infinite loop for d = 2^n.
So from the (n - 1)th iteration on, all s - values are 0 <> 1.

Benjamin
S80780 is offline   Reply With Quote
Old 2003-07-20, 19:32   #6
Annunaki
 
Jul 2003

31 Posts
Default

I just probably don`t like to think right now and look through your algorith.. but at some point got interested.. could you describe on what idea is based this algorithm.. does it has some at least half proof why p after alhorithm is done could or could not be prime? i think it wouldn`t be so efective for writing all primes in sequence as checking primarity for diferent numbers..
Annunaki is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
math gcd problem need help crack11 Homework Help 55 2020-08-13 11:18
Searching for m. primes is like playing lottery joblack Lounge 20 2009-01-05 15:18
to be faster at searching mersenne primes flosculus Information & Answers 6 2008-11-10 18:59
searching for Mersenne primes davieddy Math 7 2007-08-21 04:51
A Proposal for searching Recurrence Series Primes Erasmus Factoring 3 2004-05-14 09:26

All times are UTC. The time now is 10:40.

Sat Oct 31 10:40:12 UTC 2020 up 51 days, 7:51, 2 users, load averages: 2.01, 1.88, 1.88

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.