Diffie-Helman-Hack-262359-Faktoren-von-phi-und-p-aus-der-Analyse-von-phi-p-1","
Hier nun der zweite Teil unseres Diffie-Helman-Hacks!
\n
Sobald phi(p)+1 durch das unten beschriebene Verfahren exakt oder sehr gut angenähert ist, bildet man die Differenz von p und phi(p):
\n
mwdiff = p - phin1res
\n
\"phin1res\" entspricht \"phi(p)\"
\n
Damit hat man die Summe der Faktoren von p und phi, da phi aus p durch einmalige Subtraktion jedes Faktors gebildet wird.
\n
p= pfaktor1* pfaktor2
\n
phi(p) = (pfaktor1-1)*(pfaktor2-1)
\n
p - phi(p) = (pfaktor1)+(pfaktor2-1) = mwdiff
\n
Diese Summe kann man zur Bildung der Quadratdifferenzen der Faktoren von p oder phi(p) verwenden:
Obere Quadratbasis von p ist (mwdiff/2)+1, obere Quadratbasis von phi(p) ist (mwdiff/2) oder (mwdiff/2) -1.
\n
Mit der dritten binomischen Formel gilt dann:
\n
((mwdiff/2)+1)^2 minus p = unteres Quadrat von p.
\n
Die Differenz Unteres Quadrat muss also radizierbar sein, dann ist p korrekt und damit auch phi(p) bestätigt.
\n
Für die Faktoren von p gilt dann:
\n
((mwdiff/2)+1)^2 - (uq)^2 = p sowie pfaktor1 = mwdiff/2 +1 - uq, pfaktor2 = mwdiff/2 +1 + uq
\n
ebenso mit verkleinerter oberer Quadratbasis für phi(p), dessen Faktoren sich auch wie oben ergeben.
\n
Der entsprechende Programmteil: (Unten im Blog das gesamte Programm)
\n
mwdiff = p - phin1res
oqbphi = int(mwdiff/2)
oqbp = int((mwdiff/2)+1)
uqbp = (oqbp**2 - p)**0.5
uqbpin= int(uqbp)
if (uqbpin == uqbp):
uqbphi = (oqbphi**2 - phin1res+1)**0.5
f1phi = oqbphi - uqbphi
f2phi = oqbphi + uqbphi
f1p = oqbp - uqbp
f2p = oqbp + uqbp
ptest = f1p * f2p
if (ptest == p):
print (\"Faktoren von p: f1p, f2p; \", p, f1p, f2p,)
print(\"Faktoren von phi: f1phi, f2phi\", phin1res-1, f1phi, f2phi)
if not (ptest == p):
mwdiff = p - phin2res
oqbphi = int(mwdiff/2)
oqbp = int((mwdiff/2)+1)
uqbp = (oqbp**2 - p)**0.5
uqbpin= int(uqbp)
if (uqbpin == uqbp):
f1p = oqbp - uqbp
f2p = oqbp + uqbp
ptest = f1p * f2p
if (ptest == p):
uqbphi = (oqbphi**2 - phin2res+1)**0.5
f1phi = oqbphi - uqbphi
f2phi = oqbphi + uqbphi
phitest = f1phi*f2phi
print (\"Faktoren von p: f1p, f2p\", p, f1p, f2p)
print(\"Faktoren von phi: f1phi, f2phi\", phin2res-1, f1phi, f2phi)
print (\"Quadratbasen von p: oqbp, uqbp; Quadratbasen von phi: oqbphi, uqbphi\", p, oqbp, uqbp, phi, oqbphi, uqbphi)
\n
Ein Beispiel:
\n
Eingabe modulus p: 2291478107
Eingabe Faktor e von phi(p)+1: 198479
Eingabe p, e: 2291478107 198479
bekannter Wert modulus p und e (bekannter Faktor von phi+1): 2291478107
bekannter Wert e (bekannter Faktor von phi+1): 198479
Ergebnis: berechnetes phi+1 = e * berechneter Faktor : 2291043097 = 198479 * 11543
Ergebnis mit typischer Unschärfe: berechnetes phi+1 = e * berechneter Faktor+2 : 2291440055 = 198479 * 11545
Zusatzinfo:
Zielwerte: phi+1, e, h 2291043097 198479 11543
Abweichung phi+1, Faktor: 0 0
passende Faktoren von p: q, tq 429679 5333
Faktoren von p: f1p, f2p; 2291478107 5333.0 429679.0
Faktoren von phi: f1phi, f2phi 2291043096 5332.0 429678.0
\n
\n
DAS PROGRAMM KOMPLETT
\n
\n
import math
import sys
from sys import argv
import csv
from csv import reader
import re
import itertools
import pickle
import typing
from datetime import datetime
import cmath
import time
p = int(input(\"Eingabe modulus p: \"))
e = int(input(\"Eingabe Faktor e von phi(p)+1: \"))
#(c) Dr. Ulrike Ritter (ckcgt)
t=1
print(\"Eingabe p, e:\", p, e, \"\n\")
prox = int(p**0.5)
proxf1 = (prox + 1)**2
rest1 = proxf1 - p
fakt1 = prox + 1 + rest1
fakt12 = int(p / fakt1)
phip1 = (fakt12-1) * (fakt1-1)
test1d = int((phip1+1)/e)
if test1d %2 == 0:
test1d = test1d -1
test2d = test1d+2
phin1res = e*test1d
phin2res = e*test2d
print(\"bekannter Wert modulus p und e (bekannter Faktor von phi+1):\", p, \"\n \")
print(\"bekannter Wert e (bekannter Faktor von phi+1):\", e, \"\n \")
print(\"Ergebnis: berechnetes phi+1 = e * berechneter Faktor :\", phin1res, \"=\", e, \"*\", test1d, \"\n \")
print(\"Ergebnis mit typischer Unschärfe: berechnetes phi+1 = e * berechneter Faktor+2 :\", phin2res, \"=\", e, \"*\", test2d, \"\n \")
prox = int(p**0.5)
st= prox+1
t=3
for t in range(3, st):
t = st - t
fm1 = p % t
if (fm1 == 0 and p > t):
q = int( p/t)
tq = int(p/q)
phie = q-1
phih = tq-1
phin= (phie* phih)+1
hmod = phin % e
if (hmod == 0 and phin > e):
h = int(phin/e)
vali1h = h - int(test1d)
phical1h = phin - e*test1d
print(\"Zusatzinfo: \n\")
print(\"Zielwerte: phi+1, e, h\", phin, e, h, \"\n \")
print(\"Abweichung phi+1, Faktor:\", phical1h, vali1h, \"\n \")
print(\"passende Faktoren von p: q, tq\", q, tq , \"\n \")
#break
#Vom Mittelwert der Faktoren von phi1 auf die Quadratbasen, alternativ 1 und 2
#dann durch Vergleich mit p ob 1 oder 2 entscheiden
mwdiff = p - phin1res
oqbphi = int(mwdiff/2)
oqbp = int((mwdiff/2)+1)
uqbp = (oqbp**2 - p)**0.5
uqbpin= int(uqbp)
if (uqbpin == uqbp):
uqbphi = (oqbphi**2 - phin1res+1)**0.5
f1phi = oqbphi - uqbphi
f2phi = oqbphi + uqbphi
f1p = oqbp - uqbp
f2p = oqbp + uqbp
ptest = f1p * f2p
if (ptest == p):
uqbphi = (oqbphi**2 - phin1res+1)**0.5
f1phi = oqbphi - uqbphi
f2phi = oqbphi + uqbphi
phitest = f1phi*f2phi
print (\"Faktoren von p: f1p, f2p; \", p, f1p, f2p,)
print(\"Faktoren von phi: f1phi, f2phi\", phin1res-1, f1phi, f2phi)
print (\"Quadratbasen von p: oqbp, uqbp; Quadratbasen von phi: oqbphi, uqbphi\", p, oqbp, uqbp, phitest, oqbphi, uqbphi)
if not(uqbpin == uqbp):
mwdiff = p - phin2res
oqbphi = int((mwdiff/2))
oqbp = int((mwdiff/2)+1)
uqbp =( abs(oqbp**2 - p))**0.5
uqbpin= int(uqbp)
if (uqbpin == uqbp):
f1p = oqbp - uqbp
f2p = oqbp + uqbp
ptest = f1p * f2p
if (ptest == p):
uqbphi = (oqbphi**2 - phin2res+1)**0.5
f1phi = oqbphi - uqbphi
f2phi = oqbphi + uqbphi
phitest = f1phi*f2phi
print (\"Faktoren von p: f1p, f2p\", p, f1p, f2p)
print(\"Faktoren von phi: f1phi, f2phi\", phin2res-1, f1phi, f2phi)
print (\"Quadratbasen von p: oqbp, uqbp; Quadratbasen von phi: oqbphi, uqbphi\", p, oqbp, uqbp, phitest, oqbphi, uqbphi)