prímek
Jelentkezz be a hozzászóláshoz.
#48
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)
"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)
aki kételkedik, az gondolkodik
#47
Ennyi??? xD
Nincs rá valami jobb módszer mondjuk, hogy néhány számra meg se kelljen vizsgálni?
Nincs rá valami jobb módszer mondjuk, hogy néhány számra meg se kelljen vizsgálni?
#46
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.
Steam: Zero_hu Live!: Zero HUN
#45
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.
Úgy gondoltam hogy ha hasraütök és mondok egy 600 jegyû számot akkor annak hogy keresik a prímosztóit.
#44
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.
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.
aki kételkedik, az gondolkodik
#42
A legprimitívebb:
Erasztotenész szitája.
n-ig kihúzod a 2 többszöröseit,
aztán a 3 többszöröseit,
aztán 5 többszöröseit,
aztán p többszöröseit,
Ezt folytatod n^1/2-ig.
Amit nem húztál ki, az prím.
Erasztotenész szitája.
n-ig kihúzod a 2 többszöröseit,
aztán a 3 többszöröseit,
aztán 5 többszöröseit,
aztán p többszöröseit,
Ezt folytatod n^1/2-ig.
Amit nem húztál ki, az prím.
aki kételkedik, az gondolkodik
#41
Amugy hogy is mûködik ez az algoritmus amivel keresik az osztóit?
#40
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..........
Á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..........
#39
Itt a prímek már nem érdekelnek senkit?
aki kételkedik, az gondolkodik
#38
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.
#36
#35
gyakorlatban mire jók ezek a számok? gondolom nem hobbiból áldoznak ennyit a keresésükre..ha igen akkor elég elvetemült hobbi :D
RIP www.memod.co.uk RIP || Darkmod http://www.thedarkmod.com/
#34
Vizsgaztam 1x a profnal
#32
Gyurunek gyuru az. Csak egyebek hianyoznak neki.
({ .. -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
({ .. -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
#31
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ó?
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ó?
#30
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.
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.
#29
szoismetles :)
#28
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.
#27
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?
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?
#26
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.
#25
Hat, nem tudom mennyire lesznek ismerosek a fogalmak, itt a definicio:
R euklideszi gyuru, E az egysegek halmaza (R* := R\{0} -> 0 itt a gyuru nullelemet jeloli)
a eleme R*\E prim, ha a|bc (b,c eleme R) eseten a|b vagy a|c.
a eleme R*\E pedig felbonthatatlan, ha a=bc (b,c eleme R) eseten b eleme E vagy c eleme E.
Az egesz szamok gyurujeben (Z, +, *) ez a ket halmaz epp egybeesik, de nem minden gyuruben van igy.
R euklideszi gyuru, E az egysegek halmaza (R* := R\{0} -> 0 itt a gyuru nullelemet jeloli)
a eleme R*\E prim, ha a|bc (b,c eleme R) eseten a|b vagy a|c.
a eleme R*\E pedig felbonthatatlan, ha a=bc (b,c eleme R) eseten b eleme E vagy c eleme E.
Az egesz szamok gyurujeben (Z, +, *) ez a ket halmaz epp egybeesik, de nem minden gyuruben van igy.
#24
Akkor valaki azt is bizonyítsa be, hogy végtelen sok prímszám van. Ez tényleg nagyon egyszerû.
#23
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)
#22
bizony<#nevetes1>
#21
Zsoldos:
mi a def?
mi a def?
#20
nem ellenõrzéssel gondoltam, hanem ráérzéssel :)
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. :)
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. :)
#18
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.
#16
nemfeltétlen.
167.
prím-e ? :O
167.
prím-e ? :O
\"A digitális, mindentlogolós korban vigyázni kell az emberfiának, mert könnyen megégetheti magát. :/\" Loál János atya bölcsessége - Jelentések könyve 5.55/5 [vétó on]
#15
é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)
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)
#13
régen foglalkoztam prímszámkeresõ algoritmusokkal, persze amiket én találtam ki, mindig finomítottam rajta, és 486-os gépeken futtattuk
régi szép idõk <#whatever>
régi szép idõk <#whatever>
#12
De nem is ez a definicioja a primszamoknak.
#11
:DDD én meg a komplex számokank!!!
Persze, hogy tudtam! Csak nem sejtettem...
#10
ez kurvajó, én nyitok egy topikot a természetes számoknak ! ^.^
\"A digitális, mindentlogolós korban vigyázni kell az emberfiának, mert könnyen megégetheti magát. :/\" Loál János atya bölcsessége - Jelentések könyve 5.55/5 [vétó on]
#9
Mi az a prímszám?! <#wilting><#conf><#vigyor>
▏▎▍▋▊▉ Intel i7 2600 | 2x4GB Kingston DDR3 RAM | Radeon 5850HD 1GB | HDD 320 + 250 | Pioneer 215D | 23\" Samsung P2350
#8
Hogy én mennyire utáltam a számelméletet a szigorlat elõtt. :)
ISMÉT ÍROM A BLOGOM: http://sodi.freeblog.hu !!! Off-shore az, ha kevesebb pénzed jut megélhetési szülõk kezei közé. A sátán legnagyobb hazugsága, hogy tagadja önmaga létezését.
#7
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
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
Neked, mint kívülállónak, mi a véleményed az intelligenciáról?
#6
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
<#nyes>
::végtelen sok ikerprím(k,k+2 is prím) létezik
::minden 2k>=4 felbontható p+q prímösszeg alakban
<#nyes>
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?
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?
És azt ismeritek hogy két FIAT megy a sivatagban ?
#4
megelõztél:)
#3
elõször is a def:
azokat a N \ {1} számokat, amelyeknek pontosan két (N) osztójuk van, prímszámoknak (vagy másképp törzsszámoknak) nevezzük.
azokat a N \ {1} számokat, amelyeknek pontosan két (N) osztójuk van, prímszámoknak (vagy másképp törzsszámoknak) nevezzük.
#2
csak önmagukkal és eggyel oszthatók :)
A munka jobban megy, ha általa közöset építünk, és a világra szóló tett is többet ér, ha utána közösen énekelhetjük a Himnuszt.
#1
ezen topik célja a prímszámok érdekes tulajdonságainak megvitatása
nosza:..
nosza:..