Rabin-Miller Primality Test

I'm having problems transposing this pseudo-code into something usable. Perhaps someone could lend a hand?

Pseudo-code:

Quote:

---

Input: n > 2, an odd integer to be tested for primality;

Input: k, a parameter that determines the accuracy of the test

Output: composite if n is composite, otherwise probably prime

write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1

LOOP: repeat k times:
pick a randomly in the range [2, n − 1]
x = ad mod n
if x = 1 or x = n − 1 then do next LOOP
for r = 1 .. s − 1
x = x2 mod n
if x = 1 then return composite
if x = n − 1 then do next LOOP
return composite
return probably prime

---

What I have:

Code:

---

Private Sub Form_Load()

Dim K As Long
Dim N As Long
Dim A As Long
Dim X As Long
Dim D As Long

Dim Prime As Boolean

N = 23
K = 11
D = 3
Prime = True

For A = 3 To K Step 2
    DoEvents
    X = (A * D) Mod N
    If X < (X ^ 2) Mod N Then
        If X = 1 Then
            Prime = False
        End If
    End If
Next

Debug.Print Prime
End

End Sub

---

I am manually assigning numbers for testing. I use "DoEvents" in case I end up with a run-away loop so I can stop it without a crash.

:confused:

Are you just trying to calculate prime numbers? If so take a look at this.

Quote:

---

Originally Posted by MartinLiss

Are you just trying to calculate prime numbers? If so take a look at this.

---

Yes, I am with no upper limit.

He's using a memory array in his code. That's fine for a small quantity of numbers. It couldn't hold hundreds of millions and go on towards infinity.

I'm involved in a project, by request, to find as many as I am capable of finding. The app below is written in VB2008. I use VB6 to test algorithms with.

http://i176.photobucket.com/albums/w.../P2Capture.jpg

:)

This test is not possible to perform in VB6 and probably not in .Net either.

Step #1. Pick an odd number. Let's say 1049. This must be converted into a canonical form. Example: 2^9 = 81. The canonical form of 1049 is 131*2^3.

Step #2. An "accuracy" value must be selected. It has to be odd. Let's say 7

Step #3. Take 7 to the 131st power 7^131. A "Double" type might hold this. The catch is a modulo operation has to be performed with the original value of 1049. 7^131 Mod 1049.

Step $4: The result is 223 (by Windows Calculator). It took three division iterations to get the value of 131, which is where the three comes from in 2^3. A squaring must be done

Step $5. This can only be squared two times (3 - 1) 223 ^ 2 Mod 1049 = 426. The desired value is 1049 - 1. 426 ^ 2 = 1048. Bingo!

:)

Quote:

---

Originally Posted by storm5510

This test is not possible to perform in VB6 and probably not in .Net either.

Step #1. Pick an odd number. Let's say 1049. This must be converted into a canonical form. Example: 2^9 = 81. The canonical form of 1049 is 131*2^3.

:)

---

Before I proceed to Step #2 clarify conversion of 1049 into canonical form.
I don't understand and Wiki was not much help.

1049 is Prime so how do you get 131*2^3
Also 2^9 = 512 and 9^2 = 81.

Storm - Is it time for another Nap :cry:?

Quote:

---

Originally Posted by TriLogic

Before I proceed to Step #2 clarify conversion of 1049 into canonical form.
I don't understand and Wiki was not much help.

1049 is Prime so how do you get 131*2^3
Also 2^9 = 512 and 9^2 = 81.

Storm - Is it time for another Nap :cry:?

---

No crying! ;)

Prime numbers are odd, so what you do is to subtract 1 to make it even.

1157 becomes 1156.

You start by looping and dividing by 2 each time:

B = 1156

For A = 1 to 1000
B = (B / 2) - Fix(B / 2)
If B <> 0 Then Exit For
S = S + 1
Next

At some point, B will become fractional. That's the end of the count. S counts the number of even divisions. It is not incremented on the last loop because the "Exit For" comes before. In this case, there were 2 even divisions. The value of A plays no role. It is just a value for counting.

So, the loop value of S = 2. The binary representation of 1156 is 10010000100. See the two zero's at the end of the binary sequence? Those are removed. That leaves 100100001. In decimal, that is 289. The value of S indicates the number of zeros at the end of the binary sequence without actually having to see it.

The canonical form of 1156 is 289*2^2. If you try to work this on a hand calculator, remember the order of operations. Squaring comes first. 2^2 = 4 and 289 * 4 = 1156.

I think that's enough for now.

Quote:

---

Originally Posted by storm5510

This test is not possible to perform in VB6 and probably not in .Net either.

---

Not true, it is entirely possible... you just have to be crafty and use hex strings for modular exponentiation. This gets you up to 10^27(-1), which is respectable. Complete source code here:
http://www.naturalnumbers.org/#mr

That program seems flawed. It thinks that big ol number(Last Prime Found), which is obviously divisible by 5, is a prime number. ;)

The Currency type will get you up to 922,337,203,685,477 without much fuss.

What number ending in 5 are you talking about, pray tell...?
Who would think of testing a number ending in 5 anyway...!
Your currency type cannot go up to 26 digits, right...?
The cdec variant subtype is the best choice for large numbers in VB6.

I didn't know this discussion was still active. Some of this I wrote and now it's Greek. I am still messing with this, a little.

No one ever answered my question in the original post...

I have no idea if this will help you but I found it on the web.

I can't download it. I get a PHP file. Just send me the link. :)

Never mind, I got it. Thanks...

Here.

GCD. a.k.a. Great common denominator. I found something like this a while back, but really didn't understand how it worked. It was more complex than this too.

This would require two values to run. One would be a number to test for primality. A guess on the 2nd would be the number to test minus two?

:confused:

I have no idea.

It's really not applicable to this. I created a function and tried some numbers. I was getting a result of 1 on non-prime numbers.