#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