Egy számról hogy lehet gyorsan eldönteni, hogy prím szám-e?

[link]

pl. beírod ide.

[link]

nagyobb számoknál nem lehet gyorsan eldönteni, hogy prímek-e. ezt használják ki a számítógépes titkosításoknál is.

A leggyorsabb módszer, ha megnézed egy táblázatban ( vagy hasonló).

Ha erre nincs lehetőséged, akkor kénytelen vagy prímtényezőkre bontani, azaz megpróbálni elosztani minden prímszámmal, az illető szám gyökéig bezárólag.

Esetleg még olyan módszert tudok javasolni, ami nagy valószínűséggel megmondja, hogy egy szám prím-e:

[link]

Titkosításokhoz is hasonlókat használnak, általában beérik azzal, hogy egy 200 jegyű szám 99,999999% valószínűséggel prím.

"nagyobb számoknál nem lehet gyorsan eldönteni, hogy prímek-e. ezt használják ki a számítógépes titkosításoknál is."

Ez nem igaz.

Ahogy a 6-os is linkelt egyet, van algoritmus, amely nagyon jó eséllyel képes eldönteni, hogy a szám prím-e (plusz t idő ráfordítással mindig felezhető annak az esélye, hogy téved).

Ezzel szemben van determinisztikus algoritmus is, ami biztosan eldönti, hogy egy szám prím-e, csak az előzőnél lassabb.

[link]

Amire te gondoltál, az a prímtényezőkre bontás, ami lényegesen nehezebb probléma (tehát nem elég eldönteni hogy prím-e a szám, meg is kell mondani a felbontását ha nem az). Tehát ha van két nagy prímed, p és q, de te csak a pq szorzat értékét ismered, akkor nem ismert módszer arra, hogy a p és q számokat meghatározzuk.