Miller–Rabin primality test: Difference between revisions
m
→Using Big Integer library: changed the way the random generator is seeded
(Added Kotlin) |
m (→Using Big Integer library: changed the way the random generator is seeded) |
||
Line 1,644:
===Using Big Integer library===
{{libheader|GMP}}
<lang freebasic>' version
' compile with: fbc -s console
Line 1,650:
' But we have to define them for older versions.
#Ifndef TRUE
#Define FALSE 0
#Define TRUE Not FALSE
#EndIf
Line 1,661:
#EndMacro
Dim Shared As __gmp_randstate_struct
Function miller_rabin(big_n As Mpz_ptr, num_of_tests As ULong) As Byte
mpz_clear(n_1) : mpz_clear(a) : mpz_clear(d)▼
mpz_clear(n_2) : mpz_clear(x) ▼
If mpz_cmp_ui(big_n, 1) <
Print "
Sleep 5000
End If
Line 1,682 ⟶ 1,677:
Dim As ULong r, s
Dim As Byte return_value = TRUE
big_int(n_1) : big_int(n_2) : big_int(a) : big_int(d) : big_int(x)
Line 1,688 ⟶ 1,685:
While mpz_tstbit(d, 0) = 0
mpz_fdiv_q_2exp(d, d, 1)
s +=
Wend
While num_of_tests > 0
num_of_tests -= 1
mpz_urandomm(a, @
mpz_add_ui(a, a, 2)
mpz_powm(x, a, d, big_n)
Line 1,701 ⟶ 1,698:
mpz_powm_ui(x, x, 2, big_n)
If mpz_cmp_ui(x, 1) = 0 Then
End If
If mpz_cmp(x, n_1) = 0 Then Continue While
Line 1,708 ⟶ 1,705:
If mpz_cmp(x, n_1) <> 0 Then
End If
Wend
▲ mpz_clear(n_1) : mpz_clear(a) : mpz_clear(d)
Return TRUE▼
End Function
' ------=< MAIN >=------
Dim As Long x▼
Dim As ZString Ptr gmp_str : gmp_str = Allocate(10000000)▼
Dim As String tmp
big_int(big_n)
Randomize Timer
gmp_randinit_mt(@
tmp += Str(Int(Rnd * 10))
Next
Mpz_set_str(big_n, tmp, 10)
gmp_randseed(@rnd_, big_n) ' seed the random number generator
▲Dim As Long x
For x = 2 To 100
mpz_set_ui(big_n, x)
Line 1,739 ⟶ 1,743:
mpz_set_ui(big_n, 1)
mpz_mul_2exp(big_n, big_n, x)
mpz_sub_ui(big_n, big_n, 1)
If miller_rabin(big_n, 5) = TRUE Then
gmp_str = Mpz_get_str(0, 10, big_n)
Line 1,746 ⟶ 1,750:
Next
▲gmp_randclear(@rnd_seed)
mpz_clear(big_n)
DeAllocate(gmp_str)
' empty keyboard buffer
Print : While
Print : Print "hit any key to end program"
Sleep
| |||