TEORIA DOS NÚMEROS E CRIPTOGRAFIA - 2003/04
...RSA...
| > | restart: |
| > | with(numtheory): |
| > |
"Pequeno" Teorema de Fermat
| > | p:=341:isprime(p);
2&^(p-1) mod p; |
18769...341...
| > | ithprime(330); |
| > | evalf(log(p)); |
Velocidades...
Fazer n=101, 137...
| > | n:=2^101-1;
floor(evalf(log(n)/log(10)))+1; |
| > | st:=time():
isprime(n); time()-st; |
| > | st:=time():
ifactor(n); time()-st; |
| > | st:=time():
276756454678768767654542421009786800008797687646358793689761980029898019009098098097197676532 &^ 476587687587876687682876878769870980909109709829801879286735465189769180801703867308970767644 mod 7776546435667657657687865899389989809109893869875100910964411100909079800101010101007038709710879280197097027091776; time()-st; |
| > |
A escolha dos primos...
| > | p:=19823343437665735090909109039798460190944093714627671543546765165851:
q:=98376814111654322236572097349809801908923709019708898795543662226873: floor(evalf(log(p)/log(10)))+1;; |
| > | isprime(p),isprime(q); |
| > | p:=q:for i from 1
to 1000 do
if isprime(p+i*10) then p:=p+i*10; print(p); break;fi:od:print(i); |
| > |
Construção do código
| > | p:=19823343437665735090909109039798460190944093714627671543546765166001:
q:=98376814111654322236572097349809801908923709019708898795543662227043: |
| > | isprime(p),isprime(q); |
| > | n:=p*q; |
| > | c:=8298876371765462654611908769898978686653542543225454354354355321:igcd(c,(p-1)*(q-1)); |
| > | igcdex(c,(p-1)*(q-1),'d','z'):d; |
| > |
| > | n;c;d; |
| > |
Codificação
| > | with(StringTools): |
| > | Mg:="A CRIPTOGRAFIA
E UM ASSUNTO VERDADEIRAMENTE APAIXONANTE":
#Mg:="A TEORIA DOS NUMEROS E UMA DAS AREAS MAIS BELAS DE TODO O CONHECIMENTO HUMANO": Mg:=SubstituteAll(Mg," ",""): convert(Mg,bytes); Mg:=convert(Mg,decimal,36); |
| > |
| > | evalb(Mg<n and igcd(Mg,n)=1); |
| > | C:=Mg &^c mod n; |
| > |
Descodificação
| > | Md:=C &^d mod
n:
Md:=convert(Md,base,36): m:=nops(Md): Morig:="": for i from 0 to m-1 do Morig:=cat(Morig,convert([Md[m-i]+55],bytes)): od: Morig; |
| > |
Exemplificação/Experiências/Testes...
| > | a:=3*31: b:=3*7^2:
igcdex(a,b,'x','y'); x,y; a*x+b*y; |
| > | m:=convert("ABCXYZ",decimal,36); |
| > | convert(m,base,36); |
| > | convert([seq(i,i=32..255)],bytes); |
| > |
| > | p:=6989080897976587645765376870101101010909820979386097098379893869876917586410000000000000398768475872587264376657350909091090397984601442767154354676516519:
floor(evalf(log(p)/log(2)))+1,isprime(p); |
| > |
| > | for i from 1 to 1000
do
if isprime(p+i*10) then p:=p+i*10; break;fi:od:print(i); p;floor(evalf(log(p)/log(2)))+1; |
| > |
| > | p:=12097869876951000519:
floor(evalf(log(p)/log(2)))+1,isprime(p); for i from 1 to 1000 do if isprime(p+i*10) then p:=p+i*10; print(p); break;fi:od: floor(evalf(log(p)/log(2)))+1,isprime(p); |
| > |
Raízes primitivas
| > | p:=13:
Lf:=ifactors(p-1);Lf[2];nops(Lf[2]);#Lf[2][3][1]; |
| > |
| > | rd:=rand(2..p-2):
Lf:=ifactors(p-1);nf:=nops(Lf[2]): # nf da' o numero de factores de p-1... rp:=1: # rp=raiz primitiva... for i from 1 while rp=1 do g:=rd(): ans:=1: # ans de answer... for j to nf do res:=g &^((p-1)/Lf[2][j][1]) mod p: #res de resto... if res=1 then ans:=0: break: fi: od: if ans=1 then rp:=g: break: fi: od: rp; |
| > |