103 lines
2.6 KiB
Plaintext
103 lines
2.6 KiB
Plaintext
#include "big_int/big_integer.bi"
|
|
|
|
Function Bigint_isPrime(Byval ValorEval As Bigint) As Boolean
|
|
If ValorEval < Bigint("2") Then Return False
|
|
If ValorEval Mod Bigint("2") = Bigint("0") Then Return (ValorEval = Bigint("2"))
|
|
If ValorEval Mod Bigint("3") = Bigint("0") Then Return (ValorEval = Bigint("3"))
|
|
|
|
Dim As Bigint d = Bigint("5")
|
|
While d * d <= ValorEval
|
|
If ValorEval Mod d = Bigint("0") Then
|
|
Return False
|
|
Else
|
|
d += Bigint("2")
|
|
End If
|
|
Wend
|
|
|
|
Return True
|
|
End Function
|
|
|
|
Function Bigint_gcd(x As Bigint, y As Bigint) As Bigint
|
|
Dim As Bigint a = x, b = y
|
|
While b <> 0
|
|
Dim As Bigint next_a = b
|
|
b = a Mod b
|
|
a = next_a
|
|
Wend
|
|
|
|
Return a
|
|
End Function
|
|
|
|
Function CalcularFermat(n As Integer) As Bigint
|
|
Dim As Bigint valorBase = Bigint("1") Shl (1 Shl n)
|
|
valorBase += Bigint("1")
|
|
|
|
Return valorBase
|
|
End Function
|
|
|
|
Function PollardsRho(n As Bigint) As Bigint
|
|
If (n Mod Bigint("2")) = Bigint("0") Then Return Bigint("2")
|
|
|
|
Dim As Bigint x = Bigint("2"), y = Bigint("2"), d = Bigint("1")
|
|
Dim As Bigint c = Bigint("1")
|
|
|
|
While d = Bigint("1")
|
|
x = (x * x + c) Mod n
|
|
y = (y * y + c) Mod n
|
|
y = (y * y + c) Mod n
|
|
d = Bigint_gcd(Abs(x - y), n)
|
|
Wend
|
|
|
|
Return Iif(d = n, Bigint("0"), d) ' Avoid returning n as a factor
|
|
End Function
|
|
|
|
' Factorización prima usando Pollard's Rho
|
|
Sub FactorizarPrimos(n As Bigint, factores() As Bigint)
|
|
If n = Bigint("1") Then Exit Sub
|
|
|
|
If Bigint_isPrime(n) Then
|
|
Redim Preserve factores(Ubound(factores) + 1)
|
|
factores(Ubound(factores)) = n
|
|
Exit Sub
|
|
End If
|
|
|
|
Dim As Bigint d = PollardsRho(n)
|
|
|
|
' If we couldn't factor it, we treated it as prime.
|
|
If d = Bigint("0") Then ' Fallback if Pollard finds no factors
|
|
Redim Preserve factores(Ubound(factores) + 1)
|
|
factores(Ubound(factores)) = n
|
|
Else
|
|
FactorizarPrimos(d, factores())
|
|
FactorizarPrimos(n \ d, factores())
|
|
End If
|
|
End Sub
|
|
|
|
' Main program
|
|
Dim As Integer i, j
|
|
Dim As Bigint numFermat(0 To 9)
|
|
|
|
Print "The first 10 Fermat numbers are:"
|
|
For i = 0 To 9
|
|
numFermat(i) = CalcularFermat(i)
|
|
Print "F" & i & " = " & Str(numFermat(i))
|
|
Next i
|
|
|
|
Print !"\nFactors of the first 7 Fermat numbers:"
|
|
For i = 0 To 6
|
|
Dim As Bigint factores()
|
|
FactorizarPrimos(numFermat(i), factores())
|
|
|
|
Dim As String salida = "["
|
|
For j = Lbound(factores) To Ubound(factores)
|
|
salida &= Str(factores(j))
|
|
If j < Ubound(factores) Then salida &= ", "
|
|
Next
|
|
salida &= "]"
|
|
If Ubound(factores) = Lbound(factores) Then salida &= " (prime)"
|
|
|
|
Print "F" & i & " = " & salida
|
|
Next i
|
|
|
|
Sleep
|