Prime Number Problem solved

[mendhak]

Three computer scientists have solved a longstanding maths problem by creating a method for a computer to tell quickly and definitively whether a number is prime.

Current computer alogrithms are fast, but hae a small chance of giving either a wrong answer, or no answer at all. The new algorithm guarantees a correct and timely answer.

This comes as good news to computer scientists and mathematicians, since it simply and elegantly solves a problem that has challenged many in this field, for decades.

Here's the PDF file with the algo:

http://www.cse.iitk.ac.in/news/primality.pdf

[bugzpodder]

very intereseting article!

[DavidHooper]

Wicked link mendhak, nice one!

[Destined Soul]

I agree, nice link.

I'll see if I can code something like this, hopefully tonight.

Destined

[snakeeyes1000]

very good article. Thank's mendhak

[NotLKH]

It looks pretty simple to code from the pseudocode, except for one thing.

Can anyone explain the Bracketed mod notation between the red and blue lines?

-Thanks
-Lou

[NotLKH]

I think it means:
(x^r - 1) mod n

But I've never seen it written like that before.

Is it?

[Destined Soul]

Originally posted by NotLKH
I think it means:
(x^r - 1) mod n

I somewhat doubt that, since the notation x (mod n) would be (as you put it) (x) mod n.

However, I am somewhat confused, too. They put it throughout their paper, but I can't tell what they mean by that (at a glance.) I never did run into that during number theory.

They wouldn't be saying that "congruent to x (mod n,m)" is the same as "congruent to x in both (mod n) and (mod m)", would they? (Just a guess.)

Destined

[NotLKH]

It IS confusing trying to intuit the mod notation, especially since they use mod as seen in the attached image differently.


I had thought they were saying:

n^(r-1)/4 mod r <> 1

since 1 (mod r) returns 1 for all r except 1 {And, of course, impossible for r = 0}

BUT,... Who knows?

No, I mean it, Who Knows? Anybody? Hello?

-Lou

[Destined Soul]

Originally posted by NotLKH
I had thought they were saying:

n^(r-1)/4 mod r <> 1

Actually, they are saying that. Well, sorta, only the formula is n^(r-1)/q modulo r is NOT congruent to 1.

What's confusing about the first statement is that if I translate the mod statement into "semi-english", I'd read it as (from NotLKH's original image):

"if (x-a)^p is congruent to (x^p-a), modulo (x^r-1,p)"

But it's the ",p" that really throws me for a loop. If it wasn't there, I'd have no problem with the statement.

Destined

[bugzpodder]

I like n(r-1)/4 mod r <> 1

[NotLKH]

Yea, its a Q alright!
Thanks!
And Bugz, thanks for confirming what I thought about that.
So why did Soul stress Not Congruent if it means not equal, or <>?

[bugzpodder]

well, they sometimes use the three line thingy (extra line on the equal) to mean "congruency" in modulos

so 4 mod 3 = (add a line) 1 -- or 4=1 (mod 3)

reads 4 mod 3 is congruent to 1

but it doesn't make much of a difference though, at least i dont think.

[Destined Soul]

In modulo math, note that their symbol had three lines, not two as the equal sign contains. This symbol is "congruent to" instead of "equal to"

Some basic modulo math:
(I'll use *=* as congruent, as I can't think of a better symbol on my keyboard)

5 *=* 1 (mod 2):
5 is congruent to 1 modulo 2, but 5 does not equal 1. The command for this in vb would be result = 5 mod 2, where result = 1. It's just written a little differently from the "standard."

The "Not congruent to" symbol (I guess I could use *<>*) with the 3 bars and a line going vertically (slightly off) is where the answers are not congruent. ie:

5 *<>* 0 (mod 2)
5 is not congruent to 0 modulo 2.

The syntax I use (and them in that second image you posted) is, as far as I know, the standard way of writing this in number theory - or at least it was where I was taught it as well as among various sites on the net.

The (mod x) is like saying "log, base x" or whatever. Sure, you can take the log of a number, but you have to know what the base is in order to determine a value.

Does this make any sense?

Destined

[DavidHooper]

Line 1 involves checking if n is of the form a^b. This is hardly a one-step operation. For instance, take n = 5764801. Is it of the form a^b?

[NotLKH]

Originally posted by DavidHooper
Line 1 involves checking if n is of the form a^b. This is hardly a one-step operation. For instance, take n = 5764801. Is it of the form a^b?

It's really not too much of an operation.
Since we are checking if SomeNumber is = a^b, where a is a whole number, then since b can be expressed as
SomePrimeNumber*g, then a^b is also representable as c^SomePrimeNumber.

So, What all this means is all we have to do is check the prime roots of SomeNumber to see if any of them are whole.
But, doing some checking, if you return a double when you are checking for a root of a number, it might look like a whole
number, but when you int() it, it becomes 1 less, So....

I check to see if the root returned, rounded, taken back to the power, is equal to the number in question.

Now, as to terminating events,:

Terminating event #1
Obviously you stop if the PrimeRoot IS the whole root of the number in question, Else you continue checking.

Terminating Event #2
As you check PrimeRoots of the number in question, when the
last PrimeRoot returned becomes less than 2, then you can stop checking.

Also, this is amazingly powerful.
With only knowing the first 15 prime numbers, you can check all numbers up to 140,737,488,355,328 and you only have to loop
no more than 15 times during the process.

Of course, Useing a method based on combinations of
Log(n), and ^(n) is cpu intensive {IMHO}, but Is there a better
way of doing it?


Anyways, what do you think?

Private Sub Command1_Click()
    MsgBox IS_THIS_A_POWER_OF_A_WHOLE_NUMBER(5764801)
    MsgBox IS_THIS_A_POWER_OF_A_WHOLE_NUMBER(3 ^ 11)
    MsgBox IS_THIS_A_POWER_OF_A_WHOLE_NUMBER(2 ^ 13)
End Sub
 
Private Function IS_THIS_A_POWER_OF_A_WHOLE_NUMBER(ByVal MyIn As Long) As Boolean
Dim MyTempRoot As Double
Dim MyC As Long
'simulated external table of primes
Dim MyPrimes(14) As Long
    MyPrimes(0) = 2
    MyPrimes(1) = 3
    MyPrimes(2) = 5
    MyPrimes(3) = 7
    MyPrimes(4) = 11
    MyPrimes(5) = 13
    MyPrimes(6) = 17
    MyPrimes(7) = 19
    MyPrimes(8) = 23
    MyPrimes(9) = 29
    MyPrimes(10) = 31
    MyPrimes(11) = 37
    MyPrimes(12) = 41
    MyPrimes(13) = 43
    MyPrimes(14) = 47
'With the first 14 primes, you can check all numbers up to 2^47
'or 140,737,488,355,328
'with no greater than 15 loops.
'when we are calculating primes, then this array of primes
'is an external resource.
 
MyIn = Abs(MyIn)
'Lets worry about complexity some other time
 
MyTempRoot = 3  'initialize mytemp just to get into the loop
IS_THIS_A_POWER_OF_A_WHOLE_NUMBER = False
Do While (MyTempRoot > 2) And (IS_THIS_A_POWER_OF_A_WHOLE_NUMBER = False)
    ''''MyTempRoot = ((10 ^ ((Log(MyIn) / Log(10)) / MyPrimes(MyC))))
    'or, more simply stated:
    MyTempRoot = (MyIn ^ (1 / MyPrimes(MyC)))
    IS_THIS_A_POWER_OF_A_WHOLE_NUMBER = (MyIn = (Round(MyTempRoot) ^ MyPrimes(MyC)))
    MyC = MyC + 1
Loop
    'just a feedback mech, just to see if this works
    'in real life, this would not be used
    If IS_THIS_A_POWER_OF_A_WHOLE_NUMBER = True Then
        MsgBox MyIn & " is equal to " & MyTempRoot & "^" & MyPrimes(MyC - 1) & ", " & Chr$(13) & MyC & " Passes"
    End If
End Function

[Gandalf_Grey_]

cool algorithm.

[bugzpodder]

does your code work (like have you check against some primes)?

[NotLKH]

Originally posted by bugzpodder
does your code work (like have you check against some primes)?

Thats true, I only checked it against numbers that weren't prime,
{Such as some false composites like 26, 96, and some other numbers that would return true, As seen here:

Private Sub Command1_Click()
    MsgBox IS_THIS_A_POWER_OF_A_WHOLE_NUMBER(5764801)
    MsgBox IS_THIS_A_POWER_OF_A_WHOLE_NUMBER(3 ^ 11)
    MsgBox IS_THIS_A_POWER_OF_A_WHOLE_NUMBER(2 ^ 13)
End Sub

So, Give me a sec, and I'll double check....

MsgBox IS_THIS_A_POWER_OF_A_WHOLE_NUMBER(83) returns false, so it seems to work on primes.

Anyways, we're checking if SomeNumber is a^b, b > 1.
Now, if 1 was in the PrimeTable, I'm sure it wouldn't really work.

But, {And lets not get into this discussion} since 1 {and definetley not 0}is not really considered a formal prime number,
then it shouldn't be in the table anyways.

Now, as to why it works:

All Numbers n, if they have an identity, where a, b, are non-zero positive whole numbers, where n = a^b, must also have the property n = c^SomePrime, since b = SomePrime*d, where c & d are also nonzero, positive whole numbers.
ie...

if n = a^b
and b = P*d
then
n = c^P
where c = a^d
d is whole, P is Prime,
due to the rule z^x*y = (z^x)^y

So, if we check all primeroots of n, and see if they are whole, or
see if, when rounded and then Raised back to the SomePrime
power, they equal the original n, then we know n is of the form
c^SomePrime. And, if not, we check the next PrimeRoot, and so
on, until the returned primeroot < = 2. {Obviously, if n^(1/k) <=
2, then the only possible next whole "PrimeRoot" that could work
would be 1, We eed go no furthur.}


-Lou

[NotLKH]

Well, it seems no one knows!

Hmm, if we can't figure it out, then how can we perform the pseudocode?

Well, lets try again?
Can ANYONE Explain the mod notation in the following?

[DavidHooper]

Hi NotLKH, try emailing the people who wrote the paper. Their address are at the bottom of page 1.

[Destined Soul]

I wrote my number theory prof and he just got back to me with this regarding that notation:

Anyway the notation you are asking about means the following I
think. First you reduce the polynomial modulo x^r-1. Then reduce the
polynomial coefficients modulo p. The latter will be familiar to you
from number theory. The former is accomplished in an analogous manner.
You divide the polynomial by x^r-1 with remainder. The remainder is
the value of the given polynomial modulo x^r-1.
To do this you either need long division of polynomials or Maple of
course.

Destined

[amitabh]

The three chaps who have put in this paper will also bring out the code in a few days. Currently they are busy getting it verified through the various research journals.