probabilistic primality test

[Wso]

I thought of a probabilistic primality test a while back and have looked online trying to find if this method has been used or described anywhere before, but so far haven't seen it anywhere. The basic idea is as follows:

 

Define f(x, y) as the number of times “temp = y”, “y = x modulo y” and “x = temp” can be preformed before y is equal to 1

For example, f(25, 7) = 3

because 25 modulo 7 = 4 step 1

7 modulo 4 = 3 step 2

4 modulo 3 = 1 step 3

In general, using prime numbers as either x or y will result in a higher answer when compared to non prime numbers. This method isn’t exact by any means, and can only tell you which numbers are more likely to be prime, not which numbers are certainly prime. This method can be very useful in running through a very large list of potential primes and ranking them in terms of which ones deserve to be checked first for primality. It should also be noted that any two numbers of a close ratio to phi (1.618…) will also result in a larger than average result, for example 10 and 16, 100 and 162.

In order to determine if a number k is more likely to be prime then another number t, compute the sum of f(k, x) where x is 2…n, where n is any number, the higher the number the more time the process will take but the more accurate the method will be, generally using anything around 1000 will yield decent results. If f(k, x) > f(t, x) for x in 2…1000, k is more likely to be prime than t. So my question is how useful could this method be? What is the efficiency of this algorithm? Is it O(1) because the largest order operation preformed is modulos? Has this been used before at all?

[wtf]

"f(25, 7) = 3"

 

Why did you start with 7? Why not start with 25 mod 11 for example?

 

Also I'm not sure exactly which number you're probabalistically proving prime. 25 or 7?

 

Can you make this a little more clear? I admit I didn't follow your method in detail, I got lost when you pulled 7 out of the air without explanation.

 

If you apply your method to the first million numbers, how many "probable primes" are actually prime and how many are composite? In other words how many hits and how many false positives? Have you determined your method to be useful for large numbers where trial division isn't? Mod operations are more efficient than division so perhaps so, if it works. But I don't understand what exactly you're doing. Is 25 a probable prime?

Edited March 22, 2016 by wtf

[Wso]

"f(25, 7) = 3"

 

Why did you start with 7? Why not start with 25 mod 11 for example?

 

Also I'm not sure exactly which number you're probabalistically proving prime. 25 or 7?

 

Can you make this a little more clear? I admit I didn't follow your method in detail, I got lost when you pulled 7 out of the air without explanation.

 

If you apply your method to the first million numbers, how many "probable primes" are actually prime and how many are composite? In other words how many hits and how many false positives? Have you determined your method to be useful for large numbers where trial division isn't? Mod operations are more efficient than division so perhaps so, if it works. But I don't understand what exactly you're doing. Is 25 a probable prime?

My apologies, I chose 25 and 7 at random just to demonstrate the first part of the method.

 

In the case of "f(25, 7) = 3", I'm not proving any number to be prime, I am nearly stating the result of the method previously described.

 

In order to test for primality, comparisons must be made. If f(x, k) > f(y, k) where k is the first 100 or so primes (though any numbers can b used as k, there is a noticeable increase in accuracy when using primes over composite numbers) then x is more likely to be prime than y is.

 

 

To answer your question about false positives, I wrote a method which computes the average result of f(x, [first 100 primes]) for every number from 1 to 1,000,000. Then if the result for any individual number is greater than or equal to 1.09 (1.09 is just the constant which seemed to work best, it could just as well be any number) * the average, it is considered to most likely be prime. This is because a number x who has a higher than average f(x, y) is more likely to be prime then a number with a smaller f(x, y). The results yielded 2745 possible primes, of which 361 were correct. This isn't truly the best way to use this method however, its really meant for taking a large list of large numbers and telling you which ones to test first for primality.

 

Hopefully this clears it up, if not, I can write out some pseudo code so you can get a better feel for the algorithm.

[wtf]

My apologies, I chose 25 and 7 at random just to demonstrate the first part of the method.

 

In the case of "f(25, 7) = 3", I'm not proving any number to be prime, I am nearly stating the result of the method previously described.

 

In order to test for primality, comparisons must be made. If f(x, k) > f(y, k) where k is the first 100 or so primes (though any numbers can b used as k, there is a noticeable increase in accuracy when using primes over composite numbers) then x is more likely to be prime than y is.

Can you show a fully worked example that takes some number and shows it to be probably prime or not?

 

Hopefully this clears it up, if not, I can write out some pseudo code so you can get a better feel for the algorithm.

I don't need to see your code. Just a clear description of the algorithm. I would like to see a fully worked example that starts from some number and produces the result "probably prime" or not. I'd also like to see the statistical results of your research. Out of N numbers tested, how many were judged prime that were prime; judged prime that were not prime; judged not prime that were prime; and judged not prime that were not prime? N doesn't have to be large but perhaps up to 1000 or so would give us an idea if this is working or not. If it's working, then the fun is to figure out why!

 

And I still don't know what you mean by choosing 25 and 7 at random. What number are you testing for primality and what does it mean to randomly choose a number? It's very difficult to randomly choose natural numbers since there's no uniform probability distribution on them.

 

So just to make this concrete, can you run your algorithm, for say n = 15 and n = 11, and say whether your method shows them likely prime or likely not prime.

 

ps -- Did I understand you to say you went a lot higher and got 361 out of 2745 correct? That's not a very auspicious start. Though of course no finite amount of experimentation can ever prove the truth of anything in number theory. But is that what you said?

Edited March 23, 2016 by wtf