<jupyter_start><jupyter_text>Ejercicio 8Alumna: <NAME>  Correo: <EMAIL> Da el número $n$<jupyter_code>n = 2465809416452482897062922270410493919443<jupyter_output><empty_output><jupyter_text>Apartado primero Pasa algunos test de primalidad para ver si $n$ es compuesto   Test de primalidad de Fermat<jupyter_code>bases = [2,3,5,7,11,13]
for a in bases: 
    print(f"Para la base {a} se tiene que a^(n-1) mod n = {pow(a,n-1,n)}")<jupyter_output>Para la base 2 se tiene que a^(n-1) mod n = 1
Para la base 3 se tiene que a^(n-1) mod n = 1
Para la base 5 se tiene que a^(n-1) mod n = 1
Para la base 7 se tiene que a^(n-1) mod n = 1
Para la base 11 se tiene que a^(n-1) mod n = 1
Para la base 13 se tiene que a^(n-1) mod n = 1<jupyter_text>A la vista de los resultados se tiene que $n$ es un posible primo de Fermat para las bases $2,3,5,7,11,13$.  Test de Solovay Strassen<jupyter_code>#Código auxiliar  de prácticas anteriores 
# Exponencial rápida 
def LeftToRightFastExponential(base:Integer, exp:Integer, p:Integer):
    b = exp.binary()
    a = base
    c = 0
    acc = 1
    n = p
    for i in b:
        c = 2*c
        acc = mod(acc ^2, n)
        if i == '1':
            c += 1
            acc = mod(acc*a, n )   
    return acc

primos = [2,3,5,7,11]
def Jacobi(a :Integer,n :Integer):
    a %= n
    result = 1
    while a != 0:
        while is_even(a):
            a /=2
            if(n % 8 in [3, 5]):
                result *= -1
        a, n = n,a
        if (a % 4 == n % 4 == 3):
            result *= -1
        a %=n
    

    return (0,result)[n == 1] 

def VerboseTest_Solovay_Strassen(b:Integer,n:Integer):
    congruente = LeftToRightFastExponential(b, (n-1)//2, n)
    jacobi = Jacobi(b,n)
    print(f"\nTest Solovay Strassen Base {b} n ={n}")
    print(f"Por el algoritmo Jacobi (b/n) = {jacobi}")
    print(f"b^((n-1))/2 modulo n es  {congruente}")
    posible_primo = False
    if (congruente == jacobi or (congruente-n) == jacobi): 
        print(f"{n} es un posible primo Euler en base {b}")
        posible_primo = True
    else:  
        print(f"{n} NO es primo gracias al criterio de Euler en base {b}")
        posible_primo = False
    return posible_primo
    
for b in bases:
    VerboseTest_Solovay_Strassen(b,n)<jupyter_output>Test Solovay Strassen Base 2 n =2465809416452482897062922270410493919443
Por el algoritmo Jacobi (b/n) = -1
b^((n-1))/2 modulo n es  2465809416452482897062922270410493919442
2465809416452482897062922270410493919443 es un posible primo Euler en base 2

Test Solovay Strassen Base 3 n =2465809416452482897062922270410493919443
Por el algoritmo Jacobi (b/n) = -1
b^((n-1))/2 modulo n es  2465809416452482897062922270410493919442
2465809416452482897062922270410493919443 es un posible primo Euler en base 3

Test Solovay Strassen Base 5 n =2465809416452482897062922270410493919443
Por el algoritmo Jacobi (b/n) = -1
b^((n-1))/2 modulo n es  2465809416452482897062922270410493919442
2465809416452482897062922270410493919443 es un posible primo Euler en base 5

Test Solovay Strassen Base 7 n =2465809416452482897062922270410493919443
Por el algoritmo Jacobi (b/n) = 1
b^((n-1))/2 modulo n es  1
2465809416452482897062922270410493919443 es un posible primo Euler en base 7

Test Solovay Strassen Base 11 n[...]<jupyter_text>Test de Miller Rabin<jupyter_code># Código auxiliar de prácticas anteriores
ModuloBonito = lambda x,n : (x-n, x)[x< (n//2)]

def Test_Miller_Rabin(a: Integer, n:Integer)-> bool:
    compuesto  = False
    # Calculamos sucesión impar 
    m = (n-1)
    r = 0
    while is_even(m):
        m //= 2
        r += 1
    print('\n','='*60)
    print(f"Test Miller Rabin base a = {a}, n = {n} \n m={m}, n = m * 2^{r}")
    print('='*60)
    anterior = 1
    # Cálculo de la a-sucesión 
    for i in range(r+1):
        congruente = pow(a, m * pow(2, i), n)
        congruente_bonito = ModuloBonito(int(congruente), int(n))
        print(f" Para r={i} el término sucesión mod(a^(m 2^r), n) es: {congruente_bonito}")
        if( congruente_bonito == 1 and  abs(anterior) != 1):
           compuesto = True
        anterior = congruente_bonito
    if anterior != 1:
        compuesto = True
    salida = (
        f"{n} es un posible primo de Miller-Rabin para la base {a}",
        f"{n} es compuesto"
        )[compuesto]
    print(salida, '\n')
    return compuesto 

for p in bases:
    Test_Miller_Rabin(p,n)<jupyter_output>============================================================
Test Miller Rabin base a = 2, n = 2465809416452482897062922270410493919443 
 m=1232904708226241448531461135205246959721, n = m * 2^1
============================================================
 Para r=0 el término sucesión mod(a^(m 2^r), n) es: -1
 Para r=1 el término sucesión mod(a^(m 2^r), n) es: 1
2465809416452482897062922270410493919443 es un posible primo de Miller-Rabin para la base 2 


 ============================================================
Test Miller Rabin base a = 3, n = 2465809416452482897062922270410493919443 
 m=1232904708226241448531461135205246959721, n = m * 2^1
============================================================
 Para r=0 el término sucesión mod(a^(m 2^r), n) es: -1
 Para r=1 el término sucesión mod(a^(m 2^r), n) es: 1
2465809416452482897062922270410493919443 es un posible primo de Miller-Rabin para la base 3 


 ============================================================
Test Miller Rabin[...]<jupyter_text>Apartado segundo Factoriza $n+1$ encontrando certificados de primalidad para los factores mayores de 10000. Vamos a factorizar el número usando la Rho Pollard, antes nos damos cuenta de que $n+1$ tiene como divisores a $2^2$ y a $19$ luego el número $m$ con el que vamos a trabajar es:<jupyter_code>m = (n+1)//4//19
# Algoritmo prácticas anteriores
def Verbose_Rho_de_Polard(n:Integer, f) -> Integer:
    '''Devuelve un factor de p
    o n si es un fracaso
    '''
    mf = lambda x: f(x)% n
    #print(f"Cálculo de Rho de Polar para n={n}")
    x = 1
    y = 1
    d = 1
    paso = 0
    #print(f"Paso {paso}   x={x}    y={y}")
    while d == 1:
        paso += 1
        x = mf(x)
        y = mf(mf(y))
        d = gcd(abs(x-y),n)
        #print(f"Paso {paso}    x={x}    y={y}    mcd={d}")
    return d
f = lambda x : x^2 +1 

## Versión de sacar todos los factores de manera manual 
def SacaFactores(numero_factores, n, f ):
    factores = []
    m = n
    hay_factores = True 
    while numero_factores >= 0 and hay_factores:
        numero_factores -= 1
        d = Verbose_Rho_de_Polard(m,f)
        if d != m:
            factores.append(d)
            m = m // d
            print(f"Se tiene que n = multiplicar los elementos de {factores} y {m}\n")
        else:
            factores.append(m)
            print('='*60)
            hay_factores = False
    return factores
factores = SacaFactores(0, m,f )
print(f"Los factores de {m} son {factores}")<jupyter_output>Se tiene que n = multiplicar los elementos de [47128831] y 688429143145855402034758463849

Los factores de 32444860742795827592933187768559130519 son [47128831]<jupyter_text>Luego los factores candidatos son:<jupyter_code>factores = [2,19, 47128831, 688429143145855402034758463849 ]<jupyter_output><empty_output><jupyter_text>Además es necesario obtener un certificado de primalidad de los últimos El proceso sería volver a aplicar el algoritmo que estamos siguiendo ahora mismo y después dar un testigo, dando como resultado que en efecto ambos son primos. (Vamos a omitir el proceso ya que eso pertenece a prácticas anteriores.)<jupyter_code># Código auxiliar prácticas anteriores
def BuscaTestigo(n, factores, lista):
    m = n-1
    for i in lista:
        if pow(i,m, n) == 1:
            condicion_testigo = True 
            for f in factores:
                if pow(i,m//f, n) == 1:
                    condicion_testigo = False 
                    break
            if condicion_testigo == True:
                return i
    return 0


factores_aux = dict()
# Esta jerarquía muestra la dependencia de los testigos a calcular 
factores_que_mostrar = [factores[2], 
                            224423,  # ya descompone
                        factores[3], 
                            2840077 , 
                                26297, # ya descompone
                            265395451 , 
                                47819,
                                    23909,   # ya descopone
                            959397780037,
                                26489,
                                3018227,
                                    79427 # ya descompone
                                ]
for p in factores_que_mostrar:
    factores_aux[p] = factor(p-1) # <NAME>
    print(f"los factores de {p-1} son {factores_aux[p]}")
    factores_aux[p] = list(map(lambda x:x[0], factores_aux[p]))
# vamos a buscar testigos
for f in factores_que_mostrar[::-1]:
    testigo = BuscaTestigo(f, factores_aux[f], [2,3,5,7,11,13,15, 17,19, 23, 29, 31])
    mensaje = (
        f"{testigo} es un testigo de la primalidad del factor ={f}",
        f"No se ha encontrado un testigo que demuestre la primalidad del factor = {f}"
    )[testigo == 0] 
    print(mensaje)<jupyter_output>los factores de 47128830 son 2 * 3 * 5 * 7 * 224423
los factores de 224422 son 2 * 11 * 101^2
los factores de 688429143145855402034758463848 son 2^3 * 7 * 17 * 2840077 * 265395451 * 959397780037
los factores de 2840076 son 2^2 * 3^3 * 26297
los factores de 26296 son 2^3 * 19 * 173
los factores de 265395450 son 2 * 3 * 5^2 * 37 * 47819
los factores de 47818 son 2 * 23909
los factores de 23908 son 2^2 * 43 * 139
los factores de 959397780036 son 2^2 * 3 * 26489 * 3018227
los factores de 26488 son 2^3 * 7 * 11 * 43
los factores de 3018226 son 2 * 19 * 79427
los factores de 79426 son 2 * 151 * 263
2 es un testigo de la primalidad del factor =79427
2 es un testigo de la primalidad del factor =3018227
3 es un testigo de la primalidad del factor =26489
5 es un testigo de la primalidad del factor =959397780037
2 es un testigo de la primalidad del factor =23909
2 es un testigo de la primalidad del factor =47819
2 es un testigo de la primalidad del factor =265395451
3 es un testigo de la primalid[...]<jupyter_text>A la vista de los resultados los factores :<jupyter_code>factores<jupyter_output><empty_output><jupyter_text>son primos.<jupyter_code>testigo = BuscaTestigo(n, factores, [2,3,5,7,11,13,15])
mensaje = (
    f"{testigo} es un testigo de la primalidad de n={n}",
    f"No se ha encontrado un testigo que demuestre la primalidad de n= {n}"
)[testigo == 0] 
print(mensaje)<jupyter_output>2 es un testigo de la primalidad de n=2465809416452482897062922270410493919443<jupyter_text>Apartado tercero  Con $P=1$, encuentra el menor $Q$ natural mayor o igual que 2, tal que definan una sucesión de Lucas que certifique la primalidad de $n$. Nos basaremos en la caracterización de primalidad: Si encontramos una sucesión de Lucas, con $P$,$Q$ con $d=P^2 - 4Q$ no cuadrado perfecto y se satisface que $(n, 2Qd) = 1$ y el rango de Lucas $w(n)= n \pm 1$ entonces n es primo. Definimos las funciones que vamos a utilizar:<jupyter_code>def sLucas_modificado(P,Q,r,n):
    U_0=0
    U_1=1
    V=0
    k=0
    aux1=0
    aux2=0
    num_binario= bin(r)[2:]
    for i in num_binario:
        if i=='0':
            aux1=(2*U_0*U_1-P*U_0**2)%n
            aux2=(U_1**2-Q*U_0**2)%n
            U_0=aux1
            U_1=aux2

        if i=='1':
            aux1=(U_1**2-Q*U_0**2)%n
            aux2=(P*U_1**2-2*Q*U_0*U_1)%n
            U_0=aux1
            U_1=aux2
            
    V=(2*U_1-P*U_0)%n
    return U_0,U_1,V


def comprueba_condicionesLucas(sucesion):
    condicion=False
    for cont,i in enumerate(sucesion,start=1):
        if cont==1 and i==0: # solo el primero es congruente a 0
            condicion=True
        else: 
            if i==0:
                condicion=False
    
    return condicion


def certificado_sLucas(P,n,factores_primos):
    sucesion_U=[]
    Q=1
    r=n+1
    while comprueba_condicionesLucas(sucesion_U)==False:
        Q+=1
        sucesion_U=[]
        for i in factores_primos:
            un,a,v=sLucas_modificado(P,Q,r//i,n)
            sucesion_U.append(un)
            
    return P,Q,sucesion_U

factores.insert(0,1 ) # añadimos un uno al principio
P=1
P,Q,sucesion=certificado_sLucas(P,n,factores)
print("P: ",P,"Q:",Q)
cont=0
for i in factores: 
    print(f"U_(n+1)/{i}, =",sucesion[cont])
    cont+=1<jupyter_output>P:  1 Q: 2
U_(n+1)/1, = 0
U_(n+1)/2, = 1445563546333125415472685040396674986922
U_(n+1)/19, = 2337396916435230302473885871946517997327
U_(n+1)/47128831, = 1324746672392258078649063563730902924192
U_(n+1)/688429143145855402034758463849, = 2195440474544974924555082376726942700047
{'fraction_non_alphanumeric': 0.12390979806710144, 'fraction_numerical': 0.1348314606741573, 'mean_word_length': 2.887599266951741, 'pattern_counts': {'":': 0, '<': 38, '<?xml version=': 0, '>': 40, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '492295', 'license': 'Apache-2.0', 'n_tokens_mistral': 5890, 'n_tokens_neox': 4831, 'n_words': 1379, 'path': 'Ejercicio-8-Blanca-Cano.ipynb', 'repo_name': 'BlancaCC/Number-Theory-and-Cryptography', 'size': '12774'}