A wikipedia-ban is ír egy pár prímtesztrõl: "http://hu.wikipedia.org/wiki/Pr%C3%ADmteszt"
A legjobb jelenleg az AKS-algoritmus, de ezekrõl nem sokat tudok. Nagyon hatékonyan keresik a prímeket, illetve faktorizálják a számokat, de ezzel nem sokat lehet megtudni a prímek elhelyezkedésérõl.
Nagy számoknál nem is ez a cél, de nincs is más alternatíva. Több száz számjegynél lassan kevés lesz az univerzum eddigi ideje is a számítás elvégzéséhez. Végül is az kevesebb mint 5*10^17sec. Ha másodpercenként 10milliárdos lépésekben haladsz, az még mindig csak 5*10^27. Mivel elég a négyzetgyökig számolni, akkor 2,5*10^55-ig kilehet számolni az összes prímet (ilyen feltételekkel). S ettõl még messze van a 600. :O)
Ennyi??? xD
Nincs rá valami jobb módszer mondjuk, hogy néhány számra meg se kelljen vizsgálni?
Fapados módszer, hogy 2tõl kezdve a szám négyzetgyökéig el kell osztogatni sorban a prímszámokkal az adott számot, és ha nincs olyan prímszám, amivel osztható, akkor a szám is prímszám.
Azt tudom hogy a prímek osztói csak 1 és önmaguk.
Úgy gondoltam hogy ha hasraütök és mondok egy 600 jegyû számot akkor annak hogy keresik a prímosztóit.
Igazad van, pet0330 kérdését félre értettem.
A prímeket keresik (pl. Erasztotenész szitájával).
A prímek osztóit nem. Mivel a prímek osztói: 1, és önmaguk.
Amugy hogy is mûködik ez az algoritmus amivel keresik az osztóit?
Sziasztok!
Áll.: Végtelen sok prímszám van. Biz.: Szerintem INDIREKTEN a legegyszerûbb bizonyítani. Tegyük fel, hogy véges sok prímszám van. Ezután szorozzuk össze ezeket a számokot és adjunk hozzá 1-et. Ekkor egy olyan számot kapunk ami az eddigi prímszámokkal osztva 1 maradékot ad, tehát ez vagy egy prímszám vagy olyan prímosztói vannak amik nem voltak az eredetileg feltett prímszámok között. És ezt mindig el lehet játszani..........
Fölösleg4es ezzel a prímes titkosítással szenvedni, úgysem ott lopják el a kulcsot ahol gondolod!
A primszámaid fej vagy irással keverve, spórolásra késztethetnek.
Mivel a nyilvános kulcsú/asszimetrikus titkosítások (ilyen például az RSA) primszámokon alapulnak, ezért igen nagy a jelentõségük a primszámoknak. Bõvebben errõl itt, itt. és itt olvashatsz. Vagy ajánlom figyelmedbe Simon Singh Kódkönyv címû mûvét.
({ .. -1 , 0, 1, 4, 6, 8 ...} , +, *) nem lehet gyuru, mert az osszeadas muvelet peldaul kivezet belole. (1+4=5 nem eleme a halmaznak)
Reg tanultam mar ilyesmit, arra emlekszem, hogy talalkoztam olyan strukturaval, amiben volt felbonthatatlan elem, de nem volt prim.. Talan vmilyen (nem test) feletti polinom polinom. Z[x]-en filoztam most, de ott is egybeesnek, igy a Q[x] is ugrott.. Majd irok ha eszembejut. Test feletti polinomgyuruben biztos megegyeznek. Talan konnyebben talalnank, ha nem a halmazt varialnank, hanem a "*", "+" muveleteket definialnank kicsit maskeppen.
akartam is írni, hogy ez nem gyûrû, de ezek szerint több gond is van vele:) viszont akkor milyen példát lehet mondani, ahol a prím és felbonthatatlan nem egyezik?
R test feletti polinóm gyûrû? - az irreducibilis polinomok prímek is? (szerintem igen) vagy: ({...-4,-1,0,1,4,6,8,9,10,12...},+,*) gyûrû (már ha az) - vagyis Z\({primek}unio{-primek}) mármint prímek Z-ben:) ebben pl 4 felbonthatatlan, és 6*8=48 4|48 de sem 6 sem 8 nem osztható 4-el vagyis 4 nem prím ez jó?
Paros szamok alatt mit ertesz? ...-6 -4 -2 0 2 4 6... valahogy igy? A "szokvanyos" (+, *) muveletekkel ez nem alkot euklideszi gyurut ezert nem definialhato sem a prim, sem a felbonthatatlan fogalma. Indoklas pl euklideszi gyuru egyik szukseges feltetele az egysegelem letezese, ebben a gyuruben pedig nincs. (def: H gyuru, e egysegelem, ha e E H, es minden a E H-re ae=a) Mivel egysegelem sincs, ezert egyseg sem (integritasi tartomanyban letezik egysegelem <=> letezik egyseg). Az egyseg defje egyebkent a egyseg H integritasi tartomanyban, ha minden x E H -re a|x , tehat minden mas szamnak osztoja. De mondjuk nem kell ennyire bizonygatni, konnyen lathato, hogy nincs olyan szam a paros szamok kozott, ami minden masiknak osztoja lenne, ezert egyseg sincs, ami ott szerepel a felbonthatatlan definiciojaban.
Az ember elso ranezesre azt mondana, hogy a 2 minden paros szamnak osztoja, ez az egesz szamok kozott igaz is, de a paros szamok kozott mar nem.. Pl 2 nem osztoja 6-nak, mivel nem letezik olyan xE{paros szamok} amire 2x=6. (az oszthatosag definicioja..) Ha kilepsz a megszokott Z-bol akkor semmi sem olyan egyszeru mint latszik, mindennek utana kell gondolni.
Hat mert masra nem is nagyon lehet, pl az oszthatosag is csak integritasi tartomanyban van ertelmezve. Ez a legaltalanosabb, ezert ez a hivatalos definicio. Ha egyszerusitett rendszeren dolgozol, akkor mar mast tetelt bizonyitasz szerintem, esetleg max otletet adhatnak az ilyesmik szerintem.
igaz, igaz!, és pl a páros számok körében a def szerint nincs is prím, csak felbonthatatlan:)
de azért a részemrõl maradnék Z-ben, ugyanis vannak olyan sturktúrák ahol nem teljesülnek a "hétköznapi" prímtételek: maradékosztály gyûrûben véges sok prím van...
-------- bár érdekesek ezek is...lehet hogy a megoldatlan tételek vizsgálatát ilyen leegyszerûsített rendszereken kéne kezdeni?! egyébként miért pont gyûrûn definiálod?
Szoval amit te irtal az inkabb a felbonthatatlanok defjere hasonlit inkabb. Ha egesz szamokat nezzuk , vegulis ekvivalens, de nem csak az egesz szamok kozott leteznek primek, sokkal altalanosabb a fogalom.
Arra a definícióra gondolsz, hogy ha p prím és p=n*m, akkor abból következik, hogy n=p vagy m=p? (Más megfogalmazásban: p prím, n|p és m|p => n=p vagy m=p)
ugyebár az idõk során, osztáskor, szorzáskor találkozunk a számok többségével amik ezután valahogy "ismerõsen" csengenek. a prímekkel viszont ritkábban találkozunk, ezért viszonylag könnyen fel lehet õket ismerni. :)
Hat hogy ellenorizd, hogy van-e prim osztoja n szamnak, boven eleg gyok n -ig probalgatni (gondolom egyertelmu hogy miert), ezen belul is a primekkel. Tehat 200 alatti szam eseten max 8 osztast kell vegezned. Minel kisebb a szam annal konnyebb fejben megsaccolni.
A kocka elsõ részében is a prím számokon alapult, hogy jó terembe mennek-e?
nemfeltétlen. 167.
prím-e ? :O
érdekesek ezek a prímszámok.
Amúgy megfigyeltétek már, hogy egy 1-tõl kb. 200-ig milyen könnyen megmondja az ember egy számról, hogy prím-e vagy sem? (gondolom mert kevesebbszer fordulnak elõ a számítások során)
ez kurvajó, én nyitok egy topikot a természetes számoknak ! ^.^
Mi az a prímszám?!
Hogy én mennyire utáltam a számelméletet a szigorlat elõtt. :)
Az amerikai RSA kriptográfiai vállalat széfjében lapuló két prímszámot azok szorzatából több hónapi munkával fejtették vissza német és holland kutatók. A felbontott szám 200 jegyû, vagyis ezzel megdöntötték japán kollégáik egy héttel ezelõtt bejelentett faktorizálási rekordját.
Jens Franke és Thorsten Kleinjung matematikusok a bonni egyetemen amszterdami kollégáikkal együttmûködve új világcsúcsot értek el a nagy számok prímtényezõkre bontásában. Megtalálták a RSA200 néven emlegetett, 200 jegyû óriásszám két prímfaktorát. A számítási mûveletet a két fõiskola számítógépeire bízták, ezen kívül besegítettek a német informatikai biztonsági hivatal (BSI) nagygépei is. A bonni egyetemen ez a feladat három hónapig lekötötte az egy gigabites hálóra kapcsolt, 80 darab 2,2 GHz-es számítógépbõl álló clustert, írta a Technology Review.
Fûben, fában a prímszám
Az amerikai RSA Security kriptográfiai vállalat által 2001-ben kiírt faktorizálási versenyben az általuk kiötlött RSA200 prímtényezõinek meghatározása volt az egyik feladat. A nemzetközi kiírás több puszta szórakoztató fejtörésnél. A hagyományos, nyilvános kulcsú titkosítási és elektronikus aláírási eljárások azon a tényen alapulnak, hogy a nagy számoknak igen nehéz megtalálni a prímtényezõit.
Aki az interneten titkosított oldalon keresztül vásárol, online banki mûveletet végez, vagy aktiválja az autója indításgátlóját, mind erre az eljárásra hagyatkozik. Az új faktorizálási rekord ugyan nem teszi kérdésessé az említett eljárások biztonságát, az RSA szakértõi jelenleg mégis már a 300 jegyû számok használatát javasolják.
Elõztek a japánok
Az RSA200 megbontásával Jens Franke csapata visszaszerezte a faktorizálási rekordot, amelyet egy héttel korábban elvesztett. Május 2-án jelentette be ugyanis a japán Kazumaro Aoki, hogy munkatársaival az NTT távközlési konszern clusterét és a német kutatóknál bevált számítási eljárást használva megtalálták a 176 jegyû C176 (11281+1) prímtényezõit.
A korábbi csúcsot Franke, Kleinjung és kollégáik 2003 decembere óta tartották, amikor megdöntötték a két helyiértékkel rövidebb RSA576-ot. Ezt követõen sem ültek sokáig a babérjaikon, nekiláttak megszervezni az RSA200 felbontását.
Sokáig tartana
A nagy számok visszafejtésénél a kutatók azt a számelméleti algoritmust, a számteszt szitát (Number Field Sieve, NFS) használják, amelyet J.M. Pollard ötlött ki több mint 15 évvel ezelõtt.
Ez az eljárás rendszerezi és ezzel felgyorsítja a szükséges számítási mûveleteket. A faktorizálás ennek ellenére favágó munka, nem pedig célzott keresés. Az RSA200 esetében egyetlen 1 GHz-es pc kereken 121 év alatt készült volna el a feladattal.
Forrás: Index
szívesen látnám a következõ egyszerû tételek bizonyítását: ::végtelen sok ikerprím(k,k+2 is prím) létezik ::minden 2k>=4 felbontható p+q prímösszeg alakban
akkor 1kerdezek! van az egy, na mùost ez primszam mert egyel es onmaaval oszthato. de ha ez a ket szam azonos akkor csak 1 szammal lehet osztani nem? akkor ez "uberebb" mint a primszam nem?
Informatika és tudomány
