Coppia di primi

[Havel29]

Salve, sto cercando di risolvere il seguente problema. Dato un numero N (molto grande), sapendo che:
[formule]N=a^2+b^2[/formule]
In cui, a e b sono numeri primi, trovare dei possibili candidati per a e b. Ho provato a trovare i fattori primi di N, ma una volta ottenuti non so cosa farmene per poter estrarre in qualche modo a e b. Qualcuno ha qualche proposta?

[3m0o]

Ci credo che non riesci, appena ho il tempo e riesco a trovare un modo semplice di spiegarti ritorno, altrimenti per ora prova con il brute force

[3m0o]

Partiamo con il dire che è un problema molto complesso quello che cerchi di risolvere, per nulla semplice. Per controllare che \(N\) sia scrivibile come somma di due quadrati (attenzione non primi necessariamente) basta controllare che nella decomposizione in fattori primi di \(N\) non ci siano fattori \(p^k \) dove \(p\) è un numero primo della forma \(4n+3\) e \(k\) è dispari https://en.wikipedia.org/wiki/Sum_of_two_squares_theorem. Questo è il Teorema della somma dei due quadrati che generalizza il Teorema di Fermat sulla somma dei due quadrati https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares. Già le tecniche per dimostrare questo fatto utilizzano metodi di matematica relativamente avanzata. Un metodo sicuramente funzionante ma inefficiente per trovare una decomposizione del numero \(N\) come somma di due quadrati, nota che richiede tempi esponenziali, è controllare se \( \sqrt{N - n^2} \) è un intero con \( n \leq \sqrt{N}\). Se invece richiedi che entrambi i numeri siano pure primi beh allora un metodo ancora più inefficiente è crivellare tutte le soluzioni trovate con i primi. So che esistono algoritmi più efficienti con tempistiche polinomiali (per la semplice somma di due quadrati) ma temo di non conoscerli sinceramente.
Se supponiamo che \(N\) sia un primo della forma \(4M+1\) allora per trovare un coppia di interi \( a,b\) non necessariamente primi, tale per cui \(N^2=a^2+b^2\) (e lo so che questo non è il problema che hai chiesto, ma nota che questo è un problema molto più semplice di quello che hai chiesto te), ci sono dei modi che richiedono già la conoscenza di concetti avanzati in Teoria algebrica dei numeri come ad esempio la Jacobsthal sums, per ulteriori dettagli puoi vedere questo link https://math.stackexchange.com/questions/435139/given-the-norm-of-a-gaussian-integer-how-to-find-the-original-gaussian-integer in cui c'è un link al Paper originale in tedesco. Ma nota che è matematica molto complessa (che esce sicuramente da questa sezione del forum) e richiede molta conoscenza per essere in grado di capire cosa c'è scritto (anche sapendo il tedesco) e in generale per cercare di risolvere questo problema.

Per quanto riguarda la tua domanda originale, ovvero dato \(N \) un intero positivo scrivibile come somma di quadrati, trovare due primi (se esistono) \(p,q\) tale per cui \(N = p^2 + q^2 \), non sono a conoscenza di nessun metodo purtroppo che risolve questo problema, ma in ogni caso sono molto sicuro che se dovesse esistere non puoi dedurlo semplicemente dalla decomposizione in fattori primi di \(N\), ma anzi chiederebbe dei metodi avanzati di Teoria Algebrica dei numeri. Un idea che non ho provato ad esplorare sarebbe quella di partire dalla soluzione di Jacobsthal e potenziarla in altri modi. Ad esempio riconducendoti in qualche modo al caso in cui \(N\) è un primo della forma \(4M+1\). Ma non credo comunque che la Jacobsthal sums dia necessariamente due interi primi se esistono, per cui dovresti ancora farci un lavoro sopra e non mi è molto chiaro come.
Sono stato molto vago perché non sapendo il tuo livello di matematica non sapevo bene come prendere questa domanda, anche perché non sono in grado di darti molti più dettagli a riguardo.

[Havel29]

Ho scelto questo sezione perché il problema è stato proposto come quesito (classificato come di riscaldamento - facile) in una gara a cui ho participato un pò di tempo fa incentrata sulla sicurezza informatica, in particolare questo quesito era di crittografia. Pensavo di aver perso per strada qualche dettaglio perché non mi sembrava triviale, magari provo a ricontrollare la traccia originale ma non mi sembra ci fosse tanto di più. Appena trovo qualche altra informazione la riporto qua.

[Martino]

La difficoltà del problema dipende molto dalla fattorizzazione di $N$, la puoi scrivere?

[Havel29]

Ho trovato una soluzione, proposta da un utente giapponese. Vi cito ciò che ha scritto, anche se ad esser sincero non ho compreso a pieno il funzionamento.
"Ho sempre la sensazione che a^2+b^2 sia la norma originale di Z[i], e che quindi p^2+q^2=(p+qi)(p-qi), quindi se fattorizzo N in Z[i], combino i risultati (con il coniugato che ne sceglie uno), e ne trovo uno in cui sia p che q sono entrambi numeri primi."
Se dovesse servire potrei fornire il codice sage (se lo ritenete utile)
In ogni caso, in risposta a Martino, il numero da fattorizzare variava da istanza a istanza, ma i due numeri p e q sono entrambi dei primi da 1 a 2^32.

[axpgn]

Potresti, per favore, riportare esattamente il testo originale del problema, parola per parola?
Anche una virgola può fare la differenza (lasciamo stare Martino, quello della cappa )
Lo diciamo spesso ma non siamo molto ascoltati

[Martino]

Ho capito che variava, ma non è che il numero $N$ lo scelgono a caso, sceglieranno un $N$ specifico. Dato un $N$ specifico, uno può avere idee su come risolvere il problema. Cercare di risolverlo per ogni $N$ mi sembra un po' senza speranza.

[Havel29]

Il numero viene scelto pseudocasualmente da python. In ogni caso te ne riporto uno:
N = 160292173719855949079582682363864538836697661509098801146747468276360869075130.
Per quanto riguarda il testo ve lo riporto, ma è un codice python:

Codice:

import os
import signal
from Crypto.Util.number import *

flag = os.environb.get(b"FLAG", b"dummmmy{test_test_test}")

def main():
    p = getPrime(128)
    q = getPrime(128)
    n = p * q

    N = pow(p, 2) + pow(q, 2)

    print("Let's factoring !")
    print("N:", N)

    p = int(input("p: "))
    q = int(input("q: "))

    if isPrime(p) and isPrime(q) and n == p * q:
        print("yey!")
        print("Here you are")
        print(flag)
    else:
        print("omg")

def timeout(signum, frame):
    print("Timed out...")
    signal.alarm(0)
    exit(0)

if __name__ == "__main__":
    signal.signal(signal.SIGALRM, timeout)
    signal.alarm(30)
    main()
    signal.alarm(0)


In buona sostanza il server il server genera due primi p e q, poi calcola N=p^2+q^2 e le stampa. Noi dobbiamo scrivere al server quali pensiamo siano i p e q, e se azzecchiamo ci andrà nella porzione di codice che fa print(flag), altrimenti print(omg). Considerate che la "flag" nel codice riportato qua sopra non è quella che il server manderà, ovviamente.

[Martino]

Ho capito, ma i primi $p,q$ li devi trovare a mano o puoi usare un programma?