I'm having problems transposing this pseudo-code into something usable. Perhaps someone could lend a hand?
Pseudo-code:
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.
Last edited by storm5510; Sep 14th, 2009 at 01:53 PM.
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.
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!
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 ?
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.
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
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.
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?
Rabin-Miller Primality Test
Reply With Quote
2009 - 2016
Originally Posted by MartinLiss
?
Re: Rabin-Miller Primality Test
