Riduzione coefficienti polinomi
Dati i due polinomi in due variabli $x$ e $y$
$A(y,x)=((a1)*y+(a2))*((a3)*x+(a4))$
$B(y,x)=((b4)-(b3)*x)*((b2)-(b1)*y)$
entrambi congrui a zero modulo un numero $N$ semiprimo
Esiste un metodo per ridurre i coefficienti ,in $x$ ed $y$ minori di $sqrt(N)$ ed il coefficiente in $xy$ minore di $64$ , di una loro combinazione lineare di stesso grado dei polinomi $A(y,x)$ e $B(y,x)$ sfruttando la congruenza ?
Esempio
dati i due polinomi in due variabli $x$ e $y$
$A(y,x)=(25*y+11)*(27*x+1)$
$B(y,x)=(65-8*x)*(67-8*y)$
entrambi congrui a zero modulo $1763$
$A(y,x)=((a1)*y+(a2))*((a3)*x+(a4))$
$B(y,x)=((b4)-(b3)*x)*((b2)-(b1)*y)$
entrambi congrui a zero modulo un numero $N$ semiprimo
Esiste un metodo per ridurre i coefficienti ,in $x$ ed $y$ minori di $sqrt(N)$ ed il coefficiente in $xy$ minore di $64$ , di una loro combinazione lineare di stesso grado dei polinomi $A(y,x)$ e $B(y,x)$ sfruttando la congruenza ?
Esempio
dati i due polinomi in due variabli $x$ e $y$
$A(y,x)=(25*y+11)*(27*x+1)$
$B(y,x)=(65-8*x)*(67-8*y)$
entrambi congrui a zero modulo $1763$
Risposte
Quei due polinomi non sono congrui a zero modulo $1763$. Ad esempio il termine noto di $A$ è $11$, che è diverso da $0$ modulo $1763$.
Intendo ad esempio
$x=3$ ed $y=3$ $->$ $A=7052 ;B=1763$
che sono congrui a zero modulo $1763$
In pratica chiedo se esiste un metodo non iterativo [No bruteforce] per risolvere questo sistema
$a*25*27+64*b=g*1763+G$
,
$a*1*25-8*65*b=h*1763 +H$
,
$a*27*11-b*8*67=k*1763+K$
,
$G<=64$
,
$H<=sqrt(1763)$
,
$K<=sqrt(1763)$
$x=3$ ed $y=3$ $->$ $A=7052 ;B=1763$
che sono congrui a zero modulo $1763$
In pratica chiedo se esiste un metodo non iterativo [No bruteforce] per risolvere questo sistema
$a*25*27+64*b=g*1763+G$
,
$a*1*25-8*65*b=h*1763 +H$
,
$a*27*11-b*8*67=k*1763+K$
,
$G<=64$
,
$H<=sqrt(1763)$
,
$K<=sqrt(1763)$
Il vettore nullo è una soluzione. Poi devi essere più preciso: dove vivono le tue variabili? $\mathbb Q$? $\mathbb R$? $\mathbb Z$?
"hydro":
Il vettore nullo è una soluzione. Poi devi essere più preciso: dove vivono le tue variabili? $\mathbb Q$? $\mathbb R$? $\mathbb Z$?
$\mathbb Z$
Allora è semplicemente il teorema di struttura per moduli finitamente generati su un pid. Trovi la risposta su un qualsiasi libro di algebra del triennio.
"hydro":
Allora è semplicemente il teorema di struttura per moduli finitamente generati su un pid. Trovi la risposta su un qualsiasi libro di algebra del triennio.
Grazie.
Prima che me lo metta a studiare (perchè al momento fuori dalla mia portata) vorrei farti due domande:
- Qual è la complessità computazionale per trovare una delle combinazioni lineari volute?
- I coefficienti che caratteristiche devono avere per velocizzare tale ricerca?
Non ne ho idea. Probabilmente ti sarà chiaro quando avrai assorbito il metodo per risolvere il problema.
"hydro":
Non ne ho idea. Probabilmente ti sarà chiaro quando avrai assorbito il metodo per risolvere il problema.
Credo di aver risolto il mio problema con un piccolo bruteforce e reimpostazione dei parametri.
Dai uno sguardo qui https://www.academia.edu/48848013/Lepor ... tion_nr_88
Mi hanno suggerito di usare l'algoritmo LLL per trovare una sola soluzione per questo sistema
$a*25*27+64*b=g*1763+G$
,
$a*1*25-8*65*b=h*1763 +H$
,
$a*27*11-b*8*67=k*1763+K$
,
$64
$0
$0
dove $j$ è un intero maggiore di 1
Qualcuno quì ne sa qualcosa?
Qual'è il costo computazionale nei confronti di $j$ e di $N=1763$ ?
$a*25*27+64*b=g*1763+G$
,
$a*1*25-8*65*b=h*1763 +H$
,
$a*27*11-b*8*67=k*1763+K$
,
$64
$0
$0
dove $j$ è un intero maggiore di 1
Qualcuno quì ne sa qualcosa?
Qual'è il costo computazionale nei confronti di $j$ e di $N=1763$ ?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo