Keresés

Iesmikre gondoltam, csak nem akartam káromkodni :DDD Van valami iesmi itt: fi(N) jelöli, hogy N-nek hány nála kisebb relativ primje van. És N=fi(N)+1, ha N prim. (Ha valaki megtalálja a fi ascii kódját, az szóljon:)) Ez használható valamire?

Ehhez használható a Fermat-(vagy az Euler-?)tétel. Valami iteráció, ami mindig kizárja a lehetséges osztóknak (vagy azoknak a számoknak, amelyek x-szel nem relatív prímek?) legalább a felét, így viszonylag kevés lépés után (n) nagy valószínűséggel (1>p>1-2^(-n)) mondhatod egy számról, hogy prím. Még rémlik, hogy vannak a csúnya Carmichael (?) számok, amelyek összetettségük ellenére prímnek mutatják magukat minden esetben a próba során, és hogy ezeket is ki lehet cselezni valahogy. Sajnos a részletek a feledés homályába merültek... Így visszaolvasva túl sok a kérdőjel. :(

Például amikor az n-jegyü prímeket generálja a program, akkor igazából nem próbálja ki az összes lehetséges osztót, hanem bizonyos próbákat végez, amik sikeréből nagy valószínűséggel állíthatja, hogy a szám prím (lusta vagyok utánanézni hogy konkrétan mi ez a próba ;)

Gondolom, a Fermat-tétel bizonyítására gondolt, ahhoz pedig még pluszban be kell vezetni egy-két számelméleti fogalmat. Sajna teljesen elfelejtettem a lényeget, pedig a szigorlathoz még kelleni fog. :) Mondjuk arra emlékszem, hogy bőven elfér a levezetés két lazán írott A4-es oldalon (a hozzá tartozó definíciókkal).

1ébként lehet, hogy hülyén fogalamztam;> A "komoly" relativ. Az egészet onnan vettem, hogy az egyetemen 1 előadás erről szólt, és a prof. számelméletileg(!) bonyloultnak nevezte a titkositás gyökereihez való visszavezetést. Én pedig kiváncsi lettem, hogyan csinálják meg nálam okosabb emberek ezt a gyakorlatban.

:)
"középsulikban nem tanulnak a kongruenciáról"

tanulnak, csak nem tudjak, hogy ugy hivjak :)

z

"...es gondolom aki azon tori a fejet, hogy megcsinalja a meglevoknel jobban..."

1.) Nem célom a világot megváltani
2.) Én is tudom a képleteket, iesmiket. Csak annyi hiányzott, hogy nem tudtam olyan irtózatosan nagy primszámokat generálni (könnyen).

Más: A számelméleti (legyen algebrai) felkészültségről: én a komoly szót nem arra értettem, hogy az illető tud hatványozni, és tudja, mi az a mod. Ha ezeket ismered, a programot megirhatod, de nem érted meg a dolog lényegét. Úgy tudom, hogy a középsulikban nem tanulnak a kongruenciáról,stb...

"Hisz az egesz egy szem modulo-N hatvanyozas. "

szereny matektudasom alapjan en is igytudom... de azt is lehet tudni, hogy tenyleg sok minden van abban a cuccosban...

z

Nemtom mi lehet benne 10 Mb. Az implementacio tenyleg trivialis, es tenyleg par kepernyon elfer. Hisz az egesz egy szem modulo-N hatvanyozas.

Pasa

Azert abban mas is van mint egy szimpla RSA titkositas.

z

Hasznalni. En csak arra reagaltam, hogy BZoltan szerint az implementacio trivialis - de akkor mitol 10 megabyte az openssl-0.9.6c.tar?

Miert, itt most hasznalni akarja valaki a RSA-t vagy implementalni?

Az utobbit minek, amikor tele van a net free megvalositasokkal? [es gondolom aki azon tori a fejet, hogy megcsinalja a meglevoknel jobban, az nem ide roham, es nem azzal a kerdessel, hogy hallott-e valaki olyanrol, hogy RSA...]

(Amugy ha van egy kesz BigInt konyvtarad, az egesz RSA implementacio par kepernyonyi kod, nem nagy durranas, es hje Knuth-ban benne van ez is, mint annyi minden ;)

Pasa

:) ha jol ertettem a feladatot akkor alapvetoen nem papir ceruzaval kellmegvalositani a dolgot :) a szamitogep jo kezekben pedig csodakra kepes :D

z

ha megerted az elmeletet onnantol az implementracio gyerekjatek.
Igen? Akkor a n*100-jegyu szamok hatvanyozasat csinald te ;)

" ez komoly számelméleti felkészültséget igényel"

sem nem komoly sem nem szamelmeleti... leginkabb algebrai es ha nem ilyedsz meg elso latasra akkor nagyon hamar rajossz, hogy kozepiskolas matekon alapsziik az eges :) ha megerted az elmeletet onnantol az implementracio gyerekjatek.

Sok sikert

z

Nem valami bonyolult, kb ennyi

     #include <openssl/err.h>

     #include <openssl/rand.h>

     #include <openssl/rsa.h>

     #include <openssl/rsa.h>

-

     #define KEYSIZE  1024

     RSA *rsa;

     rsa= RSA_generate_key (KEYSIZE, 3, NULL, NULL);

     if (rsa==NULL) {

         e= ERR_get_error ();

         SSL_load_error_strings ();

         ERR_error_string (e, errbuff);

         fprintf (stderr, "RSA_generate_key returned %lx\n%s\n",

                  e, errbuff);

         exit (12);

     }

Miben van? Ha pascal vagy c, akkor meglesném. Elsősorban a generate érdekelne.

Irtam egy ki kiprobalo-programot, ilyenek vannak benne:
RSA_generate_key
i2d_RSAPublicKey
d2i_RSAPublicKey
RSA_private_encrypt
RSA_public_decrypt

Köszi. Majd beszerzem. Picit utánanéztem az elméletnek is, de úgylátom ez komoly számelméleti felkészültséget igényel:D Te foglalkoztál már iesmivel gyakorlatban?

Az elmelet erdekel, vagy a gyakorlat? Az utobbihoz az openssl-t kell beszerezni, azon belul az rsa.h-t es az rsatest.c -t tanulmanyozni...

Ért valaki az RSA algoritmushoz? Az alap működési elvet én is értem, de ha vki tud közelebbit, pls help. Üdv: superuser