[All language] Programmeer webstrijd

[rjsomeone]

Op donderdag 01 november 2001 16:44 schreef fladder het volgende:
Ik denk dat we eerst de volgende vraag maar eens moeten beantwoorden: wat kost meer tijd, de code door elk oneven getal delen of de volgende priem berekenen en daarna de code delen door de nieuwe priem.

De vraag is dus eigenlijk: hoeveel keer kun je delen in de tijd dat je de volgende priem kunt berekenen en is dat getal groter dan het aantal priemen t.o.v. het aantal oneven getallen.

ofzo

Ja ongeveer het is niet helemaal zoals je zegt:
Wat de tijd voor mogelijkheid 1 is: 1/10*getal*tijd van 1 deling
Wat de tijd voor mogelijkheid 2 is: tijd alle priemen tot wortel v.h. getal+tijd van delingen van al die priemen.

Volgens mij is mogelijkheid 1 dus stukken sneller

[Verwijderd]

Op donderdag 01 november 2001 16:48 schreef rjsomeone het volgende:

[..]

Ja ongeveer het is niet helemaal zoals je zegt:
Wat de tijd voor mogelijkheid 1 is: 1/10*getal*tijd van 1 deling
Wat de tijd voor mogelijkheid 2 is: tijd alle priemen tot wortel v.h. getal+tijd van delingen van al die priemen.

Volgens mij is mogelijkheid 1 dus stukken sneller

ff voor de duidelijkheid, hoe kom je aan die 1/10*getal ?

[Killemov]

Wellicht moet je het probleem eerst eens in kleinere problemen hakken. Ik noem een paar voorbeelden.
- optimale opslagvorm in geheugen / op disk bepalen
- welke rekenfuncties zijn nodig om dit probleem aan te pakken
(en hoe kunnen die zo optimaal mogelijk worden geimplementeerd)
- wat is de sqrt van HET grote getal
- ga je priemgetallen elimineren
- wat is de volgorde van berekenen. (0->sqrt of sqrt->0)
- hoe distribueer je welk rekenwerk
- hoe motiveer je mensen om mee te doen
- hoe verifieer je gedistribueerde berekeningen
- hoe administreer je de gedistribueerde omgeving
- ...

[rjsomeone]

Op donderdag 01 november 2001 16:56 schreef fladder het volgende:

[..]

ff voor de duidelijkheid, hoe kom je aan die 1/10*getal ?

Voor 't kleinste rsa getal geldt dit:
Je neemt alle getallen tot de helft van het getal, en dan alle de getallen eindigend op (1 of 7) en (3 of 9).
Dus je hoeft maar 2 eindcijfers te controleren, dat betekent dat je 1/10 aantal getallen van het gehele getal moet controleren.

[.oisyn]

Je neemt alle getallen tot de helft van het getal,

voor de zoveelste keer: je neemt het aantal getallen tot de WORTEL van het getal

[Verwijderd]

Op donderdag 01 november 2001 16:58 schreef rjsomeone het volgende:

[..]

Dus je hoeft maar 2 eindcijfers te controleren, dat betekent dat je 1/10 aantal getallen van het gehele getal moet controleren.

OK ik snap. Een andere mogelijkheid is 4 eindcijfers controleren tot de wortel van het getal en dat is minder

[.oisyn]

maar om even terug te komen op de opmerking van fladder, als je alle oneven getallen neemt neem je in principe de getallen die NIET deelbaar zijn door 2.

Op dezelfde manier kun je natuurlijk ook die getallen overslaan die deelbaar zijn door 3, 5, 7, enz.

Als je een goed algoritme verzint om die getallen over te slaan (wat niet zo moeilijk is), dan kun je het dus ook zo maken dat je de getallen die deelbaar zijn door een van de eerste n priemgetallen overslaat. En dan is het nog een kwestie van benchmarken () bij welke n het algoritme optimaal is

[Verwijderd]

Op donderdag 01 november 2001 16:56 schreef Killemov het volgende:
[..]
- wat is de volgorde van berekenen. (0->sqrt of sqrt->0)

volgens mij sqrt->0 want het lijkt mij voor de hand liggender dat het priemgetal groot is, anders zou een bute force manier te snel klaar zijn en daar zullen ze wel aan gedacht hebben.Bijv. als je brute force: HET getal delen door priemgetallen beginnend bij nul doet, wat vast wel door mensen geprobeerd zal zijn, dan zouden ze veels te snel hun geld kwijt zijn als priemgetal 3 al een van de 2 goede is( de andere is dan logischer wijs (Het getal)/3)

- hoe distribueer je welk rekenwerk

Je maakt een website waarvandaan pakketjes op gehaald kunnen worden met twee getallen (de start en eindwaarde)
als een variant op mijn code gebruikt zou worden dan, anders werkt het waarschijnlijk anders

- hoe motiveer je mensen om mee te doen

Als het geld naar tweakers.net gaat dan zou je het bijvoorbeeld zo kunnen stellen dat het geld in ieder geval goed terecht komt(bijvoorbeeld dat de reclame banners dan weer een tijdje weg kunnen of dat het nog "lange tijd" gratis blijft), waarschijnlijk zijn er dan wel veel tweakers die mee willen werken, als je het op de frontpage zet natuurlijk

[tomato]

Op donderdag 01 november 2001 17:08 schreef OiSyN het volgende:
Als je een goed algoritme verzint om die getallen over te slaan (wat niet zo moeilijk is), dan kun je het dus ook zo maken dat je de getallen die deelbaar zijn door een van de eerste n priemgetallen overslaat. En dan is het nog een kwestie van benchmarken () bij welke n het algoritme optimaal is

Ik heb de thread niet echt doorgelezen, maar we zijn nu op post 220 ofzo al aangekomen bij de infamous sieve of eratosthenos

Haha dat schiet op

[Verwijderd]

hmm, kewl. Je kunt bijhouden hoeveel stappen het geleden is dat je voor het laatst een getal hebt geskipped omdat het een veelvoud van 3, 5,7 of 9 was (eventueel mer). Kost qua geheugen maar heel weinig en de for-loop om door de tellers heen te lopen om te kijken of je eventueel kunt skippen en die tellers te resetten kost sowieso minder tijd dan voor al die getallen die je niet skipped de code te delen

Ik zal vanavond eens kijken of er een functie is voor het aantal te skippen getallen t.o.v uitgezet tegen de priem.

[.oisyn]

Op donderdag 01 november 2001 17:23 schreef tomato het volgende:

[..]

Ik heb de thread niet echt doorgelezen, maar we zijn nu op post 220 ofzo al aangekomen bij de infamous sieve of eratosthenos

Haha dat schiet op

de wat?
nee sorry ik ben niet thuis in de wiskundige terminologie enzo

leg eens uit

[tomato]

Op donderdag 01 november 2001 17:31 schreef fladder het volgende:
Ik zal vanavond eens kijken of er een functie is voor het aantal te skippen getallen t.o.v uitgezet tegen de priem.

Als je daar een systeem in vindt vind ik je erg knap!

[.oisyn]

Op donderdag 01 november 2001 17:31 schreef fladder het volgende:

[..]

Ik zal vanavond eens kijken of er een functie is voor het aantal te skippen getallen t.o.v uitgezet tegen de priem.

Maak m dan zo dat je het aantal priemen kunt veranderen door simpelweg een define of constant te wijzigen en opnieuw te compilen

[Verwijderd]

Ok er vanuitgaande dat je ff alleen veelvouden van 2 en 3 skipped kun je op de volgende manier skippen

begin bij 2

3 niet (2,3,4)
1 wel (5)
1 niet (6)
1 wel (7)
3 niet (8,9,10)
1 wel (11)
1 niet (12)
1 wel (13)
3 niet (14,15,16)
1 wel (17)

etc. lijkt me zeker de moeite waard. Ik ga naar huis, eten. Als iemand anders ff wil checken of er door toevoeging van 5,7,9,11 etc ook leuke reeksen uitkomen zou mooi zijn )

[tomato]

Op donderdag 01 november 2001 17:33 schreef OiSyN het volgende:
leg eens uit

Kan niet goed uitleggen, maar goed

Om priemgetallen onder n te vinden begin je bij het eerste priemgetal, 2. Dan steep je alle veelvouden van dit priemgetal weg. Vervolgens ga je verder naar het eerstvolgende overgebleven getal (dit is dus een priemgetal), 3. Streep hiervan ook alle veelvouden weg. Je gaat nu verder naar het volgende (priem)getal, 5. Enzovoorts, tot je bij wortel(n) bent.

[edit] Dit algoritme heet de zeef van Eratostenes en is zeer simpel doch effectief. Er zijn tegenwoordig echter wel betere/snellere methoden volgens mij...

[.oisyn]

er komt ALTIJD een reeks uit die zich steeds herhaalt, mits het aantal priemen dat je checkt eindig is natuurlijk

de lengte van de reeks is het product van alle priemen

[.oisyn]

Op donderdag 01 november 2001 17:41 schreef tomato het volgende:

[..]

Kan niet goed uitleggen, maar goed

Om priemgetallen onder n te vinden begin je bij het eerste priemgetal, 2. Dan steep je alle veelvouden van dit priemgetal weg. Vervolgens ga je verder naar het eerstvolgende overgebleven getal (dit is dus een priemgetal), 3. Streep hiervan ook alle veelvouden weg. Je gaat nu verder naar het volgende (priem)getal, 5. Enzovoorts, tot je bij wortel(n) bent.

oh dat algo, ja idd

[tomato]

Op donderdag 01 november 2001 17:39 schreef fladder het volgende:
Ok er vanuitgaande dat je ff alleen veelvouden van 2 en 3 skipped kun je op de volgende manier skippen

begin bij 2

3 niet (2,3,4)
1 wel (5)
1 niet (6)
1 wel (7)
3 niet (8,9,10)
1 wel (11)
1 niet (12)
1 wel (13)
3 niet (14,15,16)
1 wel (17)

etc. lijkt me zeker de moeite waard. Ik ga naar huis, eten. Als iemand anders ff wil checken of er door toevoeging van 5,7,9,11 etc ook leuke reeksen uitkomen zou mooi zijn )

Aha, bedoel je de reeks zo. Maar dat is niet echt een 'ontdekking' hoor

Een klein tellertje bijhouden of je er een kunt skippen kan inderdaad sneller zijn dan per priem alle veelvouden eerste weg te gaan halen.

[Verwijderd]

Ik heb in [topic=231518/3/25] een geoptimaliseerd zeefalgoritme volgens Erathostenes gepost. Dat rekent alle priemen onder 100.000 uit in 630ms, maar daarmee haal je het niet! Dit soort algoritmes is veel te traag om een RSA code mee te kraken.

[.oisyn]

de reeks uitrekenen is een eenmalig proces. Je gooit gewoon het aantal getallen dat je over moet slaan in een array, en vervolgens gebruik je deze array om te kijken welke getallen je wel moet checken en welke niet.

Kijk, je kunt natuurlijk nooit ALLEEN de priemgetallen controleren, want om dat allemaal uit te rekenen gaat het veel te lang duren, maar je kunt wel zorgen dat je zo veel mogelijk samengestelde getallen eruit filterd

[joepP]

Op donderdag 01 november 2001 17:39 schreef fladder het volgende:
Ok er vanuitgaande dat je ff alleen veelvouden van 2 en 3 skipped kun je op de volgende manier skippen

...voorbeeld...

Je kan het wat duidelijk uitleggen. 2 is het eerste priemgetal, je kan alle getallen ook schrijven als:

2n + 0
2n + 1

De hele reeks 2n+0 hoef je niet te checken, die zijn natuurlijk nooit priem. Zo check je dus maar de helft van de getallen

Het volgende priemgetal is 3. 2x3=6 ->

6n + 0 //hoeft niet, deelbaar door 2 en 3
6n + 1
6n + 2 //hoeft niet, deelbaar door 2
6n + 3 //hoeft niet, deelbaar door 3
6n + 4 //hoeft niet, deelbaar door 2
6n + 5

Tgaat al beter, we checken nog maar 2/6 = 1/3 van de getallen. Tkan nog beter, het volgende priemgetal = 5. We nemen dus 2x3x5 als basis van onze getallen:

30n + 0 //hoeft niet, deelbaar door 2,3,5
30n + 1
...
30n + 5 //hoeft niet, deelbaar door 5
...
30n + 28 //hoeft niet, deelbaar door 2
30n + 29

Nu hoef je nog maar 8/30 van de getallen te bekijken. En uiteraard kan je dit uitbreiden zover je wilt, alleen de winst wordt wel steeds minder...

[.oisyn]

okee en wat is nou jouw bijdrage?

overigens, al wordt je winst steeds kleiner, het is nog steeds heel groot als je dat gaat vermenigvuldigen met het aantal combinaties dat je moet checken... dan is elk duizendste procentje mooi meegenomen

[SWfreak]

Na alle 220-berichtjes gelzen te hebben , is het me iig opgevallen hoeveel mensen meteen al gaan hakken. Volgens mij is het voor uberhaupt de Java/C/assembler/?? discussie te gaan voeren beter om eerst eens de wiskunde uit te werken. Ik wil niet beweren dat ik die zo oplepel, maar toch een

Aanzetje: Alle mogelijke factoren van dat getal van 700 cijfers berekenen is natuurlijk veel te veel werk. Je kunt misschien beter kijken naar een random methode. Bijvoorbeeld:

1. Vind een random getal in de goede range
2. Check of dit een deler is van code
3. Check met een random algoritme of dit getal een priem is (Dit kost O(log^2 n) met high probability).

Dit is iig makkelijk te distribueren maar volgens mij moet je hele goede ingewikkelde wiskundige pruning methodes vinden om dit soort processen een beetje te laten versnellen. Ik denk dat dit probleem toch wel NP-moeilijk is. Als je weet dat Travelling SalesPerson al 22.000 jaar rekentijd ofzo kost om het voor iets miezerigs als 15000 steden te doen, wat moet dit wel niet kosten. Ook distributed

[.oisyn]

2. Check of dit een deler is van code
3. Check met een random algoritme of dit getal een priem is

Dat lijkt me een beetje dubbelop, want als het een deler is dan is het automatisch een priem. Bovendien ben je er dan al, want je hoeft maar 2 getallen te vinden, dus het andere getal is dan simpelweg het grote getal / priem die je net gevonden hebt

[joepP]

Op donderdag 01 november 2001 18:01 schreef OiSyN het volgende:
okee en wat is nou jouw bijdrage?

Behalve mijn vorige posting helemaal niets

overigens, al wordt je winst steeds kleiner, het is nog steeds heel groot als je dat gaat vermenigvuldigen met het aantal combinaties dat je moet checken... dan is elk duizendste procentje mooi meegenomen

Als je het nou even wat verder doorzet, dus ook met 7, 11, 13, 17, 19, 21, etc etc. Kan je ook direct op basis daarvan je distributie doen. Dus iemand krijgt gewoon een opdracht om alle getallen N x + M te doen, met dus een ontzettend grote N en M. Zo doorzoek je in ieder geval zeer efficient de gehele getalruimte.

Maar ja, het probleem is toch veeeeeeeeeeeel te groot om op te lossen. Zelfs distributed. Maar ik volg dit draadje met veel plezier.

[.oisyn]

mmmja dat zei ik dus al, dat gedeelte met n priemgetallen

en dan zat ik niet te denken aan de eerste 20 ofzo, maar eerder aan de eerste duizenden

[Verwijderd]

Even een beetje off topic

Maar om naar de getallen terug te gaan, Priemgetallen zijn priemgetallen in het decimale stelsel, maar hoe zit het als je in andere stelsels gaat rekenen?

Is er een ander getalstelsel waar deze theorie ook opgaat?

[.oisyn]

uhm, priemgetallen zijn in elk stelsel priemgetallen

je kunt ze namelijk niet delen door een ander getal dan zichzelf en 1

Maakt niet uit hoe je ze weergeeft, je kan ze gewoon niet delen

[Verwijderd]

Op donderdag 01 november 2001 18:35 schreef joepP het volgende:
Behalve mijn vorige posting helemaal niets

Denk je dat je er met een monte-carlo methode komt? Een klein foutje in je random generator en je zit (jaren) voor niets te rekenen.

Maar ja, het probleem is toch veeeeeeeeeeeel te groot om op te lossen. Zelfs distributed. Maar ik volg dit draadje met veel plezier.

Inderdaad. Ik post nog een behulpzaam linkje (dat toch weer niet gelezen wordt) en wacht verder in spanning af wat er komen gaat.

[Verwijderd]

Op donderdag 01 november 2001 18:55 schreef mietje het volgende:

[..]
Inderdaad. Ik post nog een behulpzaam linkje (dat toch weer niet gelezen wordt) en wacht verder in spanning af wat er komen gaat.

Uit de stilte valt uit te maken dat iedereen je linkje aan het lezen is ?

[Explore]

rjsomeone:
Ja ongeveer het is niet helemaal zoals je zegt:
Wat de tijd voor mogelijkheid 1 is: 1/10*getal*tijd van 1 deling
Wat de tijd voor mogelijkheid 2 is: tijd alle priemen tot wortel v.h. getal+tijd van delingen van al die priemen.

Volgens mij is mogelijkheid 1 dus stukken sneller

Uh, dit schreef ik op pagina 7 al ofzo... Zitten we niet een beetje door elkaar te ouwehoeren? Vergeet die priemgetallen oplossings methode nou eens! Het is geen porum om zulke idiote priemgetallen uit te gaan rekenen. Eentje kost al jaaaaren.

[Verwijderd]

Mag ik jullie er aan herinderen dat elke algoritme dat delen gebruikt erg langzaam wordt. Het vermenigvuldigen van twee getallen van (576/2) 288 bits kost op een 32 bits processor al (288/16)^2 = 324 vermenigvuldigingen. Delen is een nog ingewikkelder instructie dus nog veel langzamer.

Er zit wel een soort patroon in de priemgetallen als je kijkt naar het verschil van 2 opeenvolgende priemgetallen.
eerste 15 priemgetallen zijn 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 en het verschil daartussen 1 2 2 4 2 4 2 4 6 2 6 4 2 4 dat ziet er al niet random uit.

Het verschil tussen getallen niet deelbaar door 2 en 3 heeft een patroon van 4 2 niet deelbaar door 2 en 3 en 5 is 6 2 6 4 2 4 2 4 deze reeks wordt snel langer bij elke priem die je er aan toevoegd wordt de reek priem-1 keer zo lang

[Explore]

rjsomeone:
Voor 't kleinste rsa getal geldt dit:
Je neemt alle getallen tot de helft van het getal, en dan alle de getallen eindigend op (1 of 7) en (3 of 9).
Dus je hoeft maar 2 eindcijfers te controleren, dat betekent dat je 1/10 aantal getallen van het gehele getal moet controleren.

Ja, en bovendien geldt ook het volgende...

Neem bijvoorbeeld het getal 100 als voorbeeld. Factoren hiervan zijn 50x2, 25x4, 20x5 en 10x10 als ik me niet vergis. Zoals je ziet hoef je dus maar 1/10e van de 'range' af te zoeken: je vind de 2 (en dus ook 50), je vind 4 (en dus 25), etc... Bij mijn weten geldt dit altijd. Nu is 1/10 van een 700 cijferig getal een 699 cijferig getal, maar toch...

[Explore]

borganism:
Mag ik jullie er aan herinderen dat elke algoritme dat delen gebruikt erg langzaam wordt. Het vermenigvuldigen van twee getallen van (576/2) 288 bits kost op een 32 bits processor al (288/16)^2 = 324 vermenigvuldigingen. Delen is een nog ingewikkelder instructie dus nog veel langzamer.

Zoals iemand al eens schreef hier: vermenigvuldigen is herhaald optellen en delen is herhaald aftrekken (getallen, jeweetwel)...

Er zit wel een soort patroon in de priemgetallen als je kijkt naar het verschil van 2 opeenvolgende priemgetallen.
eerste 15 priemgetallen zijn 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 en het verschil daartussen 1 2 2 4 2 4 2 4 6 2 6 4 2 4 dat ziet er al niet random uit.

Hier zijn studies over gaande, maar dan met grotere getallen. Ik zou er niet aan beginnen om hier mee aan de gang te gaan. Tenzij je er een zooitje wiskundigen bij wilt halen. Zover ik me het artikel wat ik gelezen heb kan herinneren is er wel een soort van patroon, maar je kan er niet echt op bouwen. De gaps tussen afzonderlijke priemgetallen wordt ook steeds groter naarmate de getallen groter worden.

Hoe dan ook, na zo'n 250 posts is het geheel nog een beetje chaotisch. Het lijkt me ook leuk om hier aan mee te doen, mits ik het eens ben met het gebruikte algoritme. Verder zag ik de vraag of er moet worden gekeken van sqrt(code) -> 0 of 0 -> sqrt(code). (Ik had eerder geopperd dat je 1/10 kon nemen, maar dit is dus fout: het moet inderdaad sqrt zijn.) Het lijkt mij zinnig, aangezien de twee priems die we zoeken willekeurig zijn gekozen en dus overal in de getallenruimte (mooi woord) kunnen voorkomen, om op meerdere plaatsen tegelijkertijd te zoeken. Je loopt dan wel tegen een probleem aan met het bijhouden waar er allemaal wordt gezocht.

Dit is echter vrij simpel op te lossen door een spreiding te nemen. Even simpel voorbeeldje:

Stel je zoekt 2 getallen onder 1000. Begin dan bv. op 10 plaatsen te zoeken. sqrt(1000) is ongeveer 31. 30/10 = 3. Dus dan begin je met zoeken op 3, 6, 9, etc... Op die manier is de kans op succes groter en je hoeft niet enorm veel data bij te houden (alhoewel 'ons' getal natuurlijk iets meer cijfers heeft). Bovenstaande moet weer wel geoptimaliseerd worden. Dus niet 6 maar 7, etc...

[.oisyn]

Stel je zoekt 2 getallen onder 1000. Begin dan bv. op 10 plaatsen te zoeken. sqrt(1000) is ongeveer 31. 30/10 = 3. Dus dan begin je met zoeken op 3, 6, 9, etc... Op die manier is de kans op succes groter en je hoeft niet enorm veel data bij te houden (alhoewel 'ons' getal natuurlijk iets meer cijfers heeft). Bovenstaande moet weer wel geoptimaliseerd worden. Dus niet 6 maar 7, etc...

De kans op succes is niet groter. Het lijkt wel groter omdat je wat gespreid zoekt, maar in principe maakt dat geen ene flikker uit voor de vindkans.


.edit:

Voorbeeld:
je zoekt een getal tussen 1 en 10, inclusief (dus 1 en 10 doen ook mee)
Je doet in totaal 10 tests voor elke zoekvolgorde, en bij elke test is het nummer van de test het goede getal.

Je hebt 3 zoekvolgordes:
- 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (oplopend)
- 3, 6, 9, 2, 5, 8, 1, 4, 7, 10 (gespreid)
- 3, 7, 1, 9, 8, 2, 5, 4, 10, 6 (random)

Bij de eerste zoekvolgorde heb je m bij de eerste test in 1 keer goed, bij de 2e test in 2x, bij de 3e test in 3x, enz. In totaal probeer je 55 getallen, dat geeft dus een gemiddelde van 5.5 getallen die je probeert voordat je m vind

Bij de tweede zoekvolgorde heb je m bij de eerste test in 7x (de 1 staat op de 7e plaats), bij de 2e test in 4x, dan 1x, 8x, 5x, 2x, 9x, 6x, 3x, 10x. Ook daar is het aantal getallen dat je probeert 55, en dus gemiddeld 5.5

Bij de derde zoekvolgorde vind je m in respectievelijk 3x, 6x, 1x, 8x, 7x, 10x, 2x, 5x, 4x, 9x. Weer is het aantal 55, dus gemiddeld 5.5

Conclusie: zoekvolgorde maakt geen reet uit

[Verwijderd]

Op donderdag 01 november 2001 20:52 schreef borganism het volgende:
Er zit wel een soort patroon in de priemgetallen als je kijkt naar het verschil van 2 opeenvolgende priemgetallen.
eerste 15 priemgetallen zijn 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 en het verschil daartussen 1 2 2 4 2 4 2 4 6 2 6 4 2 4 dat ziet er al niet random uit.

Natuurlijk zitten er wel patronen in de verdeling van de priemen, maar elk tot nu toe gevonden patroon wordt ergens in de reeks doorbroken.

Volgens mij is de duidelijkste indicator dat er een of ander "hoger" patroon zou kunnen zijn wel Ulam's Spiral, ontdekt in de jaren 70 in de uren van verveling tijdens een wiskunde-congres. Ulam schreef de natuurlijke getallen in en spiraal op ruitjespapier, dus:

code:

16 15 14 13
 5  4  3 12
 6  1  2 11
 7  8  9 10

En omcirkelde vervolgens alle priemen. Het gevolg waren allerlei intrigerende fractal-achtige diagonale lijnen

(de rode puntjes op het plaatje zijn mersenne-priemen)

<edit>oeps, verkeerde link gepaste</edit>

[tomato]

Op donderdag 01 november 2001 22:25 schreef mietje het volgende:
Natuurlijk zitten er wel patronen in de verdeling van de priemen, maar elk tot nu toe gevonden patroon wordt ergens in de reeks doorbroken.

Inderdaad, er zijn oneindig veel patronen in de verdeling van een reeks priemgetallen te vinden, maar tot nu toe is er geen algemeen patroon gevonden.

Volgens mij is de duidelijkste indicator dat er een of ander "hoger" patroon zou kunnen zijn wel Ulam's Spiral, ontdekt in de jaren 70 in de uren van verveling tijdens een wiskunde-congres. Ulam schreef de natuurlijke getallen in en spiraal op ruitjespapier, dus: [..]

Vind die spiral maar vaag en sowieso zou het slechts een indicator voor een patroon kunnen zijn. Tot nu toe is er iig geen algemeen patroon voor de verdeling gevonden waar iedereen het mee eens is. Als je iets moois vindt: you're in!

[Verwijderd]

Op donderdag 01 november 2001 20:52 schreef Explore het volgende:

[..]

Ja, en bovendien geldt ook het volgende...

Neem bijvoorbeeld het getal 100 als voorbeeld. Factoren hiervan zijn 50x2, 25x4, 20x5 en 10x10 als ik me niet vergis. Zoals je ziet hoef je dus maar 1/10e van de 'range' af te zoeken: je vind de 2 (en dus ook 50), je vind 4 (en dus 25), etc... Bij mijn weten geldt dit altijd. Nu is 1/10 van een 700 cijferig getal een 699 cijferig getal, maar toch...

Je 1/10e theorie is heel leuk maar der klopt niks van. Alleen voor honderdklopt ie, kijk maar:

Een van de twee getallen is kleiner dan de wortel, de andere groter. Bij bijvoorbeeld een getal als 221 komt dat al neer op 1/16e.

[Mister_X]

ik snap er geen ruk van, word er al wat gedaan hiermee? andres ga ik het wel in me 1tje proberen, hoe zie ik dan nog wel.

[Verwijderd]

Een reeks vinden die alleen afhankelijk is van z'n voorganger zal wel nooit lukken. Elke keer dat je een priem tegenkomt wil dat zeggen dat je n+k(n^2-n) mag overslaan (met n die priem en k een natuurlijk getal). Echter voor alle voorgaande priemen gaat dat ook nog op, dus zou je nog steeds alle priemen op moeten slaan.

Als je slecht wilt filteren op veelvouden van priemen kun je wel redelijk bepalen tot welke priem dat nuttig is.
deel dat je door priem n skipped is 1/(n^2-n)
(voor de mensen die denken dat dit niet klopt: het houdt rekening met wat je al dankzij lagere priemen kunt skippen)
2 -> 1/2
3 -> 1/6
5 -> 1/20

bij 19 zit je zo ongeveer tegen de 76% overslaan en veel hoger wordt dat percentage niet meer.

[Verwijderd]

Hee wat dan ook wel geinig is (is vast niet revolutionair maar ik zie het pas net:))

Stel je hebt een priem n. De eerste skip die deze priem verookzaakt is n+1*(n^2-n) = n^2.

Dus als je wilt kijken of een getal k een priem is dan hoef je slechts te controleren of deze deelbaar is door een getal in de reeks van 2 tot sqrt(k).

[Verwijderd]

Hoi,

Ik ben een jaar geleden of zo eens bezig geweest met een proggie wat zo snel mogelijk een stel priemgetallen kon uitrekenen. Uiteindelijk kwam ik op

alle priemgetallen van 0 tot 1.000.000 binnen 0.2 seconden op een PII-333! (en als je ze vervolgens allemaal in een listbox wilt stoppen is ie 5 seconden bezig )

Als je dat vergelijkt met wat van de tijden in deze thread is dat niet slecht lijkt me zo... Het gebruikte algo is een paar berichten hiervoor al een beetje genoemd, maar hier toch nog maar even een schets van een implementatie: maakt het voor veel mensen een stukje begrijpelijker denk ik. Ik denk niet dat het voor dit probleem te gebruiken is, dat product is gewoon veel te groot. Maar goed, misschien geeft het wat inspiratie voor betere aanpakken.

Maak een array met booleans voor alle getallen die je wilt checken. Elke bool zegt of het bijbehorende getal (=de index van de array) een priem is of niet. In het begin zet je ze allemaal op true. We gaan nu dus alle getallen wegstrepen die geen priem zijn.
Je kan nu natuurlijk voor elk getal gaan kijken of hij te delen is door een kleiner getal, maar dat is veel te langzaam. We gaan het dus omdraaien: we gaan voor elk getal kijken welke andere getallen hij kan delen, of een beetje concreter:

for(int i=2;i*getal<array.length;i++)
{
array[getal*i] = false;
}

Vooral bij de kleine getallen streep je op die manier heel snel heel veel getallen weg, maar goed, als je dit voor alle getallen in je array moet gaan doen ben je nog steeds wel ff bezig.
Gelukkig kan je nog een optimalisatie toepassen: Als een getal al op false staat, hoef je niet meer alle producten van dit getal weg te gaan strepen, omdat een kleiner getal dit al voor je heeft gedaan: Als je bijvoorbeeld eerst alle producten van 2 op false zet, heeft het niet zo veel zin dit ook nog eens voor 4,6,8, etc te doen.

Uiteindelijk krijg je dus een algo dat er als volgt uit ziet:

code:

zet alle booleans in array op true;
for(int j=0;j<array.length;j++)
{
  if(array[j])
  {
    for(int i=2;i*j<array.length;i++)
    {
    array[j*i] = false;
    }
  }
}

Bij de eerste paar getallen zal de binnenste loop nog redelijk vaak doorlopen moeten worden, maar dit zal snel minder worden. De looptijd van het algo zal daardoor maar iets boven de O(n) zitten en dit lijkt me dus redelijk optimaal.
Maar nogmaals, zoals eerdere berekeningen in deze thread al hebben laten zien is het waarschijnlijk een beetje onpraktisch om met dit algoritme even alle priemgetallen tot 600 digits uit te rekenen, omdat dit (nog steeds) veel te lang zou gaan duren en bovendien erg veel ruimte op je hd zou gaan kosten...

[Verwijderd]

OK voorstel. We gaan *slim* distributed brute force checken.

Iemand connect met een server en krijgt terug een twee veelvouden van 6915878970 en een range-id. Waarom dit getal? Dit is het product van de eerste 10 priemgetallen (2 t/m 31), waardoor je met zo'n getal als start alle skip-counters op 0 kunt zetten. Wat de server bijhoudt zijn pending ranges + id en de laagste veelvoud die nog niet weggegeven is.

10 counters bijhouden lijkt me nog wel te doen. Daardoor hoef je per 6915878970 getallen nog maar 5256068017 delingen uit te voeren.
Als mijn berekeningen kloppen is op deze manier ongeveer
87% van de getallen waar we door delen een priemgetal (hmm is wel erg hoog, ik zal iets fout doen ofzo )

Anyway that's my idea.

[Killemov]

Ehm Fladder ... ik snap er niks van.

Maar goed, allemaal booleans (bitjes) in een array zetten en dan de niet-priemen wegstrepen is ook leuk tot zo'n (2^32)*8.

[Explore]

Op vrijdag 02 november 2001 13:56 schreef Killemov het volgende:
Ehm Fladder ... ik snap er niks van.

Maar goed, allemaal booleans (bitjes) in een array zetten en dan de niet-priemen wegstrepen is ook leuk tot zo'n (2^32)*8.

Ik heb zo'n vaag vermoeden dat die priemen die gezocht worden boven die range liggen. Anders zou je in principe een reeks priemen van een van de vele sites kunnen plukken en aan het delen gaan slaan. Simpele brute force.

De priemgetallen die we zoeken zijn waarschijnlijk zo groot dat ze nergens op 't net in 100% precisie staan. Denk aan getallen als 2.5*10^324-1 bv. Success met rekenen...

[Verwijderd]

Hmmjah... er zijn idd wel errug veel priemgetallen...

Mijn eigen comp staat inmiddels op de gok het een en het ander te checken::

prog1 zoekt steeds het eerst volgende priemgetal
gevonden? zoek door en send priem naar prog2
prog2 deelt het ultragrote getal door het priemgetal
als de uitkomst zonder restwaarde is, checkt ie of de uitkomst een priemgetal is.. zo ja, HEBBUS....
Maarreh.. ik ben bij priemgetal 1.200.000 ofzo, en nog geen gevonden... Dus geen v/d factoren is kleiner als 1.200.000...

[Explore]

Op vrijdag 02 november 2001 14:50 schreef Ztepjuh het volgende:
... Dus geen v/d factoren is kleiner als 1.200.000...

Nee, natuurlijk niet! 1.2M is 7 cijfertjes. Fijn, maar we hebben het hier over een getal van 700 cijfers. Begin die priemmetjes maar lekker te zoeken vanaf bijvoorbeeld 459283742391857834924587982782458729379659875323672786357
964358758967894867298722456y87899838748902344592837423918
578349245879827824587293796598753236727863579642875896789
4867298722456y8789983874890234459283742391857834924587982
782458729379659875323672786357964287589678948672987224563
8789983874890234

(Slechts 300 cijfers...)

[Verwijderd]

Op vrijdag 02 november 2001 14:54 schreef Explore het volgende:

[..]

Nee, natuurlijk niet! 1.2M is 7 cijfertjes. Fijn, maar we hebben het hier over een getal van 700 cijfers. Begin die priemmetjes maar lekker te zoeken vanaf bijvoorbeeld

(Slechts 300 cijfers...)

Jaah... maar vergeet niet dat het getal wat de uitkomst is van <grootGetal>/priemgetal heel snel kleiner wordt, en dit is dus ook de bovengrens....

[Verwijderd]

Op vrijdag 02 november 2001 14:50 schreef Ztepjuh het volgende:

[..]

prog1 zoekt steeds het eerst volgende priemgetal
gevonden? zoek door en send priem naar prog2
prog2 deelt het ultragrote getal door het priemgetal
als de uitkomst zonder restwaarde is, checkt ie of de uitkomst een priemgetal is.. zo ja, HEBBUS....

[..]

Euhm... ik kan je wel vast verklappen dat als je geen restwaarde hebt, de uitkomst automatisch een priemgetal is.
Maargoed die ene extra berekening in het geval dat je een van de getallen van $ 5,000 hebt gevonden.. och, het kan geen kwaad.

[Verwijderd]

Op zich werkt het wel, zie hier recent 'citaat' uit mijn logs....

Deling: / 1300927 = 000000144665160243893749486863782104338244810941400539321101568929967955918248845042546957145989441763252700049570814737027301454802860733718365349900999053921784365117572046 Discard, by cause of decimals behind comma(1170417)

De maximale waarde voor de 2de factor is dus al drastisch gedaald....

(dit is trouwens ff een test voor het 174-cijferige getal)


Mijn systeem zal er wel lang over doen, maar in pricipe moet hij zelfs het 2048-bit kunnen decoden...
(Hij werkt namelijk met geen grotere getallen als enkele tientallen).. alles steeds in strings hebben (DUSZ HELE HOOP GEKLOOT)... maargoed. het werkt....

[Verwijderd]

loggen kost tijd

[Verwijderd]

het gedeelte van mijn progjes die loggen, hebben bijna nix te doen...
Het gedeelte dat priemget. zoekt, is veel harder bezig... maar logt helemaal nix

[Explore]

Einde discussie? Of zit iedereen hard te programmeren?

[.oisyn]

ook wel fijn dat iedereen met 'oplossingen' komt die 100 posts eerder allang eens gezegd zijn... lezen jullie de hele draad wel door? Zo komt deze discussie natuurlijk ook nooit verder

[Verwijderd]

Tsja... ik vond het ook al stil worden...

Maar ja, qua oplossingen hebben de goeie nog niet gevonden denk ik....

Heb je nog nieuwe suggesties of iets dergelijksz, OiSyN???

[.oisyn]

mmmja laat ik even opsommen wat we al hebben...

ten eerste hebben we hier 2 groepen mensen, de ene (wat kleinere) groep wil het uitzoeken met complexe wiskundige methoden die we zelf niet eens begrijpen. Natuurlijk zijn er snelle methoden bedacht door knappe mensen, maar ik denk niet dat dat voor ons haalbaar is.

Ikzelf zit dan ook in de 2e groep mensen, die gewoon liever willen brute forcen met z'n alle. Voor mij begon dit als een geintje, en ik zie het nog steeds als een geintje . Ik heb al eerder gepost dat als we echt vette research gaan doen naar complexe zooi dat de lol er al voor vele (waaronder ik) snel af is, omdat sommige onder ons het niet begrijpen en omdat we er gewoon TE serieus mee aan het werken zijn. Het gaat mij totaal niet om het kraken van die code, hoewel dat wel het doel is, maar ik zie liever gewoon dat een zootje tweakers, het liefst meer dan 100 man, lekker bezig zijn met rekenen en grazen, opscheppen over de keyrate omdat je weer een nieuwe processor hebt, en al die taferelen die je nu voor RC5 en OGR25 ziet. En dat je dan ook nog kunt zeggen van: kijk, dat hebben wij opgezet. En dan zou het natuurlijk ook nog helemaal fantastisch zijn als we ook nog eens een keer die code kraken, ook al is het 10 jaar na datum en is de geldprijs allang aan iemand anders gegeven


Maar goed, even over het (inferieure ) algoritme...
Het is dus duidelijk dat we willen brute forcen, dus gewoon het grote getal proberen te delen door kleine getallen. Omdat die deling een relatief lang proces is, is het noodzaak om zoveel mogelijk getallen weg te strepen VOORDAT je gaat proberen te delen. En dan bedoel ik dus de getallen waarvan je makkelijk kan zien of het priem is of niet.

Dit betekent natuurlijk niet dat je persee ALLEEN priemgetallen hoeft te controleren, dus het is niet noodzakelijk om echt van te voren te kijken of een getal priem is. Wel is het handig om de marge samengestelde getallen zo klein mogelijk te houden, zodat we sneller door de keyspace heen gaan.

Okee, we moeten dus makkelijk kunnen zien wat mogelijk priem is en wat absoluut niet. Elke simpele ziel kan bedenken dat we dan natuurlijk niet getallen moeten proberen die deelbaar zijn door 2, oftewel je houdt alle oneven getallen over. Op diezelfde manier zou je natuurlijk getallen deelbaar door 3 kunnen overslaan, door steeds 2 opeenvolgende getallen te controleren, dan weer niet, dan weer 2 wel, dan weer niet, enz.

Als je dat combineert (dus niet deelbaar door 2 en 3), en je begint bij 1, dan doe je dus eerst volgende 3 niet (2, 3 en 4), dan 1 wel (5), dan 1 niet (6), dan 1 wel (7) en vervolgens weer 3 niet (8, 9 en 10). Je krijgt een herhalende reeks, namelijk "3 niet, 1 wel, 1 niet, 1 wel"

Ik stel voor om dit in een array te zetten, elk element in die array is het aantal dat je moet optellen bij het huidige getal om de volgende mogelijke priem te krijgen. Bij de vorige reeks wordt dat dus { 4, 2 }
Deze array wordt steeds herhaalt. Als je bij 1 begint krijg je dus 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, enz.

Het was je misschien al opgevallen dat de meeste van deze getallen ook daadwerkelijk priem zijn, behalve 25 en 35. In het begin krijg je ook erg veel priemgetallen, maar zodra je wat hoger komt zitten er echt ongelooflijk veel samengestelde getallen tussen.

Het is dus handig om die reeks uit te breiden zodat er meer samengestelde getallen worden overgeslagen. En dan heb ik het niet over een reeks opgebouwd uit de eerste 20 priemen ofzo, maar eerder de eerste 1.000.000 of zelfs meer

Het bepalen van de reeks is een eenmalig proces, en in principe ook in een mum van tijd berekend.


client / server model
Omdat dit allemaal gedistributeerd moet werken, lijkt me het meest voordehandliggend dat er ergens een keyserver draait die gewoon tegen clients zegt vanaf welke getallen ze moeten proberen. En dan bedoel ik natuurlijk niet letterlijk welke getallen, maar meer 1.000.000 getallen, beginnend vanaf x. De keyserver moet de uitgegeven keys natuurlijk ook administreren... Dit is een enorm probleem, aangezien er gigantisch veel keys zullen zijn (een getal van 700 cijfers gedeeld door 1.000.000 is nog altijd 694 cijfers, oftewel onmogelijk op te slaan). Dit is dus nog een punt waar we heel hard over na moeten denken.

De client vraagt dus simpelweg keys op van de server, gaat ze berekenen, en op een gegeven moment stuurt hij de resultaten terug (in dit geval dus simpelweg "niet gevonden", of "hoeraa!!! dit getal was het: 24872348723" ofzoiets


Na ja, het was een lang verhaal, en uiteraard sta ik open voor suggesties!

[.oisyn]

oh ja, nog even om af te schikken:

Stel we checken 1000 keys per seconde met 1000 computers voor 10 jaar lang (24 uur per dag)

Het aantal keys dat we dan checken is

10 * 365,25 * 24 * 60 * 60 * 1000 * 1000 = 315.576.000.000.000

Stel dat we 85% van de nodige getallen overslaan, dan hebben we dus een snelheid van

315.576.000.000.000 / 0.15 = 2.103.840.000.000.000 getallen per 10 jaar

Dit is nog steeds een getal van 16 cijfers, dus voor een getal van 350 cijfers (we hoeven maar tot de wortel van een 700 cijferig getal, een getal met 350 cijfers) moeten we dan nog 10³⁵⁰ / 10¹⁶ = 10³³⁴ keer zoveel rekenkracht hebben om het in 10 jaar te halen... Mijn conclusie: NIET HAALBAAR

Volgende topic graag

[razor-x]

Op zaterdag 03 november 2001 01:48 schreef OiSyN het volgende:
*knip

je verpest het weer

[Verwijderd]

Ik heb er nog eens over na zitten denken en kwam op het volgende idee.

Die code van RSA bestaat uit 2 priemen. Maar dat weet ondertussen iedereen hier. Maar hoe weet je nou of een getal een priem is? Je deelt het door alle (priem)getallen tot de wortel, en als je bij ieder getal rest hebt is het een priemgetal.

Denk je dat RSA op die manier hun priemgetalletjes van ongeveer 10^300 (ofzo) heeft gekozen? dacht het niet. Ze hebben iets gebruikt als 2^x-1 ofzo. Misschien moeten we daarmee aan de slag.

[Verwijderd]

Op zaterdag 03 november 2001 20:22 schreef GHOst. het volgende:
Ik heb er nog eens over na zitten denken en kwam op het volgende idee.

Die code van RSA bestaat uit 2 priemen. Maar dat weet ondertussen iedereen hier. Maar hoe weet je nou of een getal een priem is? Je deelt het door alle (priem)getallen tot de wortel, en als je bij ieder getal rest hebt is het een priemgetal.

Denk je dat RSA op die manier hun priemgetalletjes van ongeveer 10^300 (ofzo) heeft gekozen? dacht het niet. Ze hebben iets gebruikt als 2^x-1 ofzo. Misschien moeten we daarmee aan de slag.

Daar kan je niet vanuit gaan

[.oisyn]

idd, ze zeggen dat je het moet factorizeren, en dan komen er 2 getallen uit... Als het geen priemgetallen zijn komen er meerdere getallen uit (want de samengestelde zijn immers weer te factorizeren)

Bovendien, als 1 van de getallen samengesteld is en geen priem, dan zijn er ook verschillende combinaties mogelijk om het grote getal te krijgen.

Ga er maar vanuit dat ze daar in dat RSA lab een behoorlijk systeempje hebben staan, met een behoorlijke database aan priemgetallen

[tekno]

als je nou ongeveer kijkt met welke priemen je een product krijgt wat zo rond de uitkomst ligt (dus niet dat we straks ook 2x3, 2x5, enz... gaan gebruiken.....) dan heb je er toch al een stuk minder. Dan zet je deze in een soort tabel. En hiervan stuur je steeds een stuk door naar de client, die dan die combinaties priemen gaat uitrekenen. De pakketjes worden dan niet zo groot. Je kunt niet alle priemen gaan doorsturen want dan krijg je een mega groot bestand.

b.v.
2 3 5 7 enz.
2 x x z z
3 x x z z
5 x x z z
7 y y p p
11 y y p p
13 y y p p
enz.

de getallen vormen gewoon de tabel. De letters geven de clients aan die het getal uitrekenen. Je stuurt steeds blokjes met de range van priemgetallen. (met of zonder tussenliggenden.....groter bestand vs. meer processortijd nodig( dus bv. range 2 - 11 en dat is alles of 2-3-5-7-11)) voor zowel 'de x en y as' van de tabel. Op de server staan deze spaces bekend onder een nummer. de client gaat rekenen met die priemen en kijkt of ie de juiste uitkomst krijgt, zo ja......bingo...sjakka...enz... we hebben hem! zo nee, stuur dan naar server door dat dat gedeelte is onderzocht en niet meer onderzocht hoeft te worden. Dat lijkt mij een van de makkkelijste methoden om een server/client based manier te maken om de code te kraken. We zouden dan onze methode eerst kunnen proberen met een van de oudere rsa-xxx factorizing challenges die al opgelost zijn rsa-140 of zo. Daar zijn we dan relatief kort mee bezig. Maar daarmee kunnen we dan wel onze werkwijze evalueren. We zullen dan alleen moet zorgen voor een goede client-server communicatie. Er zal ergens een server moeten komen met best heel veel ruimte op z'n hd voor alle data. (daarom lijkt me werken met ranges van priemgetallen ook beter, minder ruimte op server nodig....). En dan zullen de clients en server ook daadwerkelijk geschreven moeten worden. Van tevoren zullen dus eerst alle priem getallen gevonden moeten worden. Hiervoor zou je dan ook al een distributed systeem kunnen maken. dat dan ook als we bv. de test rsa (rsa-xxx makkelijker) of de makkelijkste van nu rsa-5xx geloof ik) gewoon doordraait zodat die getallen ook gewoon gebruikt kunnen worden bij volgende challenges/onderzoek. het grootste probleem is de hoeveelheid mogelijkheden en priemgetallen. Daarom zul je toch denk ik meer aan ruimtebesparing moeten denken en ietwat minder aan proc-tijd in dat opzicht. Maar ja. Ik weet niet of ik nu gewoon alles van iedereen dubbel lig op te lullen. Maar ja...dit lijkt mij een simpele manier om het op te lossen die ook nog kan werken.

Aanpak kort samengevat:
1: voor test versie
-zoek priemgetallen nodig voor challenge
-maak paren van priemen die ongeveer op uitkomst kunnen uitkomen, elimineer de rest
-maak op basis hiervan op bovenstaand systeem pakketjes
-zorg voor server-client systeem om het op te lossen
-kraken maar
2: voor daadwerkelijke challenge
-zoek priemgetallen nodig voor challenge
-maak paren van priemen die ongeveer op uitkomst kunnen uitkomen, elimineer de rest
-maak op basis hiervan op bovenstaand systeem pakketjes
-zorg voor server-client systeem om het op te lossen
-kraken maar

my 10 eurocent...

[tekno]

rsa-130 key:
18070820886874048059516561644059055662781025167694013491701270214\
50056662540244048387341127590812303371781887966563182013214880557



rsa-140 key:
2129024631825875754749788201627151749780670396327721627823338321538194\
9984056495911366573853021918316783107387995317230889569230873441936471


als we die nou gewoon proberen te kraken met onze simpele methode om te kijken of het werkt. En dan kunnen we meteen kijken welke punten aangepast kunnen worden voor hogere snelheid. de uitkomst is al bekend. Dus dan kunnen we snel kijken of onze methode goed werkt en of onze methode uberhaupt snel genoeg is om aan de kleinste nieuw rsa code te beginnnen, zelfs met de hulp van zeer veel machines.

Als we zo beginnen zouden we eventueel zelfs ala distributed.net met een zeer grote groep kunnen proberen om de code te kraken. Tweakers.net /14 rsa-xxx crackin' waarom nie? er zitten hier zo ver ik weet genoeg goede programmeurs en mensen die vrij goed kunnen optimaliseren. Dus met een beetje samen werken en steeds verbeteren zouden we toch iets van de grond moeten krijgen. Ik hoop dat dit eens een keer wel wordt uitgewerkt en niet zoals andere zaken toch nooit gebeurd.

en toen was/bleef het stil?????????

[Killemov]

Ik heb al veel goede suggesties gezien in deze thread. Het wordt nog eens wat!

Ik heb er ook nog een paar:

Kijk ook eens hier: [topic=231518/3/25]

Als eerste moet sqrt(BIG) worden uitgerekend. Aangenomen dat beide gezochte priemgetallen ook behoorlijk groot zijn moet dit het startpunt zijn. De volgorde loopt dus van trunc(sqrt(BIG)) naar 0.

Het algoritme moet simpel, snel en distribueerbaar zijn. Dit zijn wellicht karakteristieken die niet geheel met elkaar te verenigen zijn. Ik denk dat de prioriteit moet zijn: distribueerbaar, simpel, snel. (Met distribueerbaar bedoel ik dus ook dat er geen permanente communicatie tussen de client en de server hoeft te zijn.)

[tekno]

precies ja. daarom kun je beter ietwat grotere pakketjes pakken waar iedereen wat langer over doet. Bijvoorbeeld op snelste pc van dit moment 2 dagen of zo. Maar is er enig animo voor het daadwerkelijk proggen van al dit?

[raptorix]

Ik wil wel meehelpen ben niet zo een wiskunde freak maar wel redelijk verstand van databases en internetapplicaties.

[Verwijderd]

Ik wil wel meehelpen in de programmeer-crew...

(Speciality - Client/Server programming)

[Verwijderd]

Op zaterdag 03 november 2001 01:38 schreef OiSyN het volgende:
Okee, we moeten dus makkelijk kunnen zien wat mogelijk priem is en wat absoluut niet. Elke simpele ziel kan bedenken dat we dan natuurlijk niet getallen moeten proberen die deelbaar zijn door 2, oftewel je houdt alle oneven getallen over. Op diezelfde manier zou je natuurlijk getallen deelbaar door 3 kunnen overslaan, door steeds 2 opeenvolgende getallen te controleren, dan weer niet, dan weer 2 wel, dan weer niet, enz.

Als je dat combineert (dus niet deelbaar door 2 en 3), en je begint bij 1, dan doe je dus eerst volgende 3 niet (2, 3 en 4), dan 1 wel (5), dan 1 niet (6), dan 1 wel (7) en vervolgens weer 3 niet (8, 9 en 10). Je krijgt een herhalende reeks, namelijk "3 niet, 1 wel, 1 niet, 1 wel"

Ik stel voor om dit in een array te zetten, elk element in die array is het aantal dat je moet optellen bij het huidige getal om de volgende mogelijke priem te krijgen. Bij de vorige reeks wordt dat dus { 4, 2 }
Deze array wordt steeds herhaalt. Als je bij 1 begint krijg je dus 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, enz.

Het was je misschien al opgevallen dat de meeste van deze getallen ook daadwerkelijk priem zijn, behalve 25 en 35. In het begin krijg je ook erg veel priemgetallen, maar zodra je wat hoger komt zitten er echt ongelooflijk veel samengestelde getallen tussen.

Erhm... 2 en 3 zijn ook priemgetallen hoor! Die worden nu met jouw mooie methode overgeslagen maar ze horen er dus wel bij...

De volgende getallen komen niet in aanmerking voor priemgetal:

Even getallen behalve 2
Getallen die eindigen op 5

Voor de rest van de getallen moeten we dus nu nog wat regeltjes formeren. Je kunt iig elk getal wat al aan deze 2 regeltjes voldoet proberen te delen door een van de voorafgaande priemgetallen. Als dit in geen van de gevallen een heel getal oplevert heb je een priem te pakken.

Als je wil gaan rekenen met getallen die zo groot zijn moet je zelf een programmeertaal schrijven of alles in assembly doen. Een gewone Intel of AMD proc is 32-bit (Itanium uitgezonderd) en kan dus rekenen met integers tot 2^32=4294967296 (als je ervan uitgaat dat het getal niet in two's complement notatie staat en alle bits op 1 staan). Dit zijn maar 10 getallen! Een getal van 600 cijfers is in de orde van grootte van 2^2000. We moeten dus een progsel hebben dat deze getallen in bruikbare brokjes splitst waar we testjes op los kunnen laten en vervolgens de resultaten combineren. Dit is ws redelijk complex, en we moeten het minstens 2000/32=62 keer doen. Veel suc6

[.oisyn]

wat probeer je nou eigenlijk te zeggen?

Erhm... 2 en 3 zijn ook priemgetallen hoor! Die worden nu met jouw mooie methode overgeslagen maar ze horen er dus wel bij...
De volgende getallen komen niet in aanmerking voor priemgetal:

Even getallen behalve 2
Getallen die eindigen op 5

Natuurlijk zijn 2 en 3 ook priemgetallen, maar denk maar niet dat een van de delers van die RSA getallen onder de 1 miljoen ligt

En kijken of een getal eindigt op 5 heb je gewoon totaal nix aan, omdat je binair zit te rekenen, dus je kunt niet even kijken of het laatste cijfer een 5 is of niet.

Bovendien zeg je nou dat 5 ook geen priemgetal is, wat dus wel zo is.
Wat je dan eigenlijk zegt is:

Alle getallen deelbaar door 2, behalve 2
Alle getallen deelbaar door 5, behalve 5

En dan kun je er dus net zo goed bij doen:
Alle getallen deelbaar door 3, behalve 3
Alle getallen deelbaar door 7, behalve 7

En zo kun je nog wel een tijdje doorgaan, en dat is PRECIES wat ik met mijn algoritme doe


Dat van die grote getallen die niet normaal deelbaar zijn met simpele instructies op 32 of 64 bits procs: DUH! Als je alle posts had doorgelezen dan had je gelezen dat wij dat al vanaf het begin door hadden, en dat sommige onder ons (waaronder ik) allang weten hoe we dat gaan oplossen.

Als je wil gaan rekenen met getallen die zo groot zijn moet je zelf een programmeertaal schrijven of alles in assembly doen

Wat een onzin, je kunt toch gewoon je eigen datastructuur definieren en functies maken die daarmee werken? Dan ben je ook klaar, en dit kan in vrijwel elke programmeertaal.

[Verwijderd]

Op zondag 04 november 2001 19:35 schreef GiMLi het volgende:

[..]
Als je wil gaan rekenen met getallen die zo groot zijn moet je zelf een programmeertaal schrijven of alles in assembly doen. Een gewone Intel of AMD proc is 32-bit (Itanium uitgezonderd) en kan dus rekenen met integers tot 2^32=4294967296 (als je ervan uitgaat dat het getal niet in two's complement notatie staat en alle bits op 1 staan). Dit zijn maar 10 getallen! Een getal van 600 cijfers is in de orde van grootte van 2^2000. We moeten dus een progsel hebben dat deze getallen in bruikbare brokjes splitst waar we testjes op los kunnen laten en vervolgens de resultaten combineren. Dit is ws redelijk complex, en we moeten het minstens 2000/32=62 keer doen. Veel suc6

Dit klopt... maar misschien heb ik hiervoor een geimproviseerde oplossing:
ik gooi alles in strings, en vanuit daar maak ik zeg maar handmatig een 'staartdeling'. Het werkt wel, ik heb een paar antwoorden gecontroleerd....
Dit kan al een gedeelte v/h probleem oplossen..
Het probleem van de capaciteit v/d computer is hierdoor weg, blijft het probleem dat het veel te lang duurt....

[htca]

Op maandag 05 november 2001 08:14 schreef Ztepjuh het volgende:

[..]

Dit klopt... maar misschien heb ik hiervoor een geimproviseerde oplossing:
ik gooi alles in strings, en vanuit daar maak ik zeg maar handmatig een 'staartdeling'. Het werkt wel, ik heb een paar antwoorden gecontroleerd....
Dit kan al een gedeelte v/h probleem oplossen..
Het probleem van de capaciteit v/d computer is hierdoor weg, blijft het probleem dat het veel te lang duurt....

Ik denk dat dit een deel is van de oplossing. De 'staartdelingmethode' is behoorlijk bruikbaar. Anderzijds moeten we denk ik het aantal getallen dat we proberen zoveel moeten reduceren. De meeste niet priemgetallen zijn deelbaar door een laag priemgetal (2,3,5,7,11,etc.). Of een getal door 2 of 5 deelbaar is, is gemakkelijk te checken, evenals door 3 (alle cijfers uit het getal sommeren en kijken of dit door 3 deelbaar is).

We zouden een selectie algoritme kunnen fixen waarin we een mogelijk priemgetal eerst proberen te delen door de eerste N priemgetallen (database). Dit is beter dan het checken van alle getallen.

Waar het omslagpunt ligt van N is, is afhankelijk van de snelheid van het algoritme van testen en het staartdelingsalgoritme. Als de tijd die nodig is om te de grote deling te doen 4 x langer is dan de kleine deling dan zou je dus simpel gezegd eerst 4 keer kunnen checken of het getal onder de streep een priem is. Eea is natuurlijk afhankelijk van de grootte van het getal onder de streep. Hoe groter dit getal is hoe minder winst er te halen is.

ik blijf in ieder geval meedenken.

htca (post voor het eerst, maar volgt deze thread met veel belangstelling )

[Verwijderd]

ok. nog even een kleine bijdrage van mij. Als je er echt serieus werk van wilt maken dan is dit toch wel een hele grote stap in de goede richting.

The C source code of the programs used to generate and format the challenge numbers are available on request from the challenge administrator. Just send e-mail to : [e-mail].

[Verwijderd]

Op maandag 05 november 2001 09:56 schreef GHOst. het volgende:
ok. nog even een kleine bijdrage van mij. Als je er echt serieus werk van wilt maken dan is dit toch wel een hele grote stap in de goede richting.
[..]

heb ik een hele tijd geleden al naartoe gemeeld, nog nix trug gekregen

[Verwijderd]

Op zondag 04 november 2001 19:35 schreef GiMLi het volgende:

[..]

Als je wil gaan rekenen met getallen die zo groot zijn moet je zelf een programmeertaal schrijven of alles in assembly doen. Een gewone Intel of AMD proc is 32-bit (Itanium uitgezonderd) en kan dus rekenen met integers tot 2^32=4294967296 (als je ervan uitgaat dat het getal niet in two's complement notatie staat en alle bits op 1 staan). Dit zijn maar 10 getallen! Een getal van 600 cijfers is in de orde van grootte van 2^2000. We moeten dus een progsel hebben dat deze getallen in bruikbare brokjes splitst waar we testjes op los kunnen laten en vervolgens de resultaten combineren. Dit is ws redelijk complex, en we moeten het minstens 2000/32=62 keer doen. Veel suc6

http://indigo.ie/~mscott/

Zoiets maar dan nog BIGger..

[Verwijderd]

Op maandag 05 november 2001 11:15 schreef fladder het volgende:
http://indigo.ie/~mscott/

Zoiets maar dan nog BIGger..

Nog bigger? Als het met MIRACL niet lukt kun je het schudden denk ik. Dit is de bignum library.

[Verwijderd]

Factoriseren kan ook zonder priemen en delen. zie hier een simpel brute force algo

code:

 (gewijzigde versie)
superint groot = round(sqrt(rsa_xxx);
superint rest = (groot^2)-rsa_xxx;  
for(superint klein=groot;rest!=0;){
  if (rest > 0){
    rest -=groot;
    klein--;}
  else{
    rest +=klein;
    groot++;}
}

Dit algo kost ook O(n^1/2) dus nog te langzaam maar is wel een stuk sneller dan brute force door priemen delen omdat het uitreken van de priemen best veel tijd gaat kosten bij grote getallen.
Ik ben bezig met deze algo uit te breiden waarmee ik O(n^1/4) hoop te halen.

[.oisyn]

Op maandag 05 november 2001 08:14 schreef Ztepjuh het volgende:

[..]

Dit klopt... maar misschien heb ik hiervoor een geimproviseerde oplossing:
ik gooi alles in strings, en vanuit daar maak ik zeg maar handmatig een 'staartdeling'. Het werkt wel, ik heb een paar antwoorden gecontroleerd....
Dit kan al een gedeelte v/h probleem oplossen..
Het probleem van de capaciteit v/d computer is hierdoor weg, blijft het probleem dat het veel te lang duurt....

uhm ja maar waarom zou je in base10 werken op een base2 systeem? Dat maakt het alleen maar langzamer

Oftewel, strings zijn zeker niet de oplossing, je kan ook gewoon een staartdeling maken van bits. En laat dat nou net de standaard delingmethode zijn voor x-bits getallen

[.oisyn]

Op maandag 05 november 2001 12:15 schreef borganism het volgende:
Factoriseren kan ook zonder priemen en delen. zie hier een simpel brute force algo

code:

 superint groot = round(sqrt(rsa_xxx);
superint rest = rsa_xxx-(groot^2);
for(superint klein=groot;rest!=0;){
  if (rest > 0){
    rest -=groot;
    klein--;}
  else{
    rest +=klein;
    groot++;}
}

Dit algo kost ook O(n^1/2) dus nog te langzaam maar is wel een stuk sneller dan brute force door priemen delen omdat het uitreken van de priemen best veel tijd gaat kosten bij grote getallen.
Ik ben bezig met deze algo uit te breiden waarmee ik O(n^1/4) hoop te halen.

Dat algo klopt niet. Als je bijvoorbeeld 10 gaat factorizeren (2 en 5 moet daar uit komen)

round (sqrt (10) = 3.16227766016838) = 3

groot = 3, klein = 3, rest = 10 - (3²) = 1
rest > 0, dus groot = 3, klein = 2, rest = -2
rest < 0, dus groot = 4, klein = 2, rest = 0

en dan stopt ie
maar 4 en 2 maakt 8, dus het klopt niet helemaal


Als je groot++ verandert in groot-- en klein-- verandert in klein++ dan klopt het wel (alleen dan is klein het grote getal en groot het kleine getal, dus je moet die namen ook even omdraaien)

Wat je dan krijgt is

code:

superint groot, klein, rest;

klein = groot = sqrt (startgetal);
rest = startgetal - (groot * groot);

while (rest != 0)
{
    if (rest > 0)
    {
      rest -= klein;
      groot++;
    }
    else
    {
      rest += groot;
      klein--;
    }
}

[Verwijderd]

Op maandag 05 november 2001 17:33 schreef OiSyN het volgende:
Dat algo klopt niet. [mega-snip]

Je kunt het natuurlijk ook verbeteren door er klein = groot = ceil(sqrt(startgetal)); van te maken

[.oisyn]

Op maandag 05 november 2001 18:19 schreef mietje het volgende:

[..]

Je kunt het natuurlijk ook verbeteren door er klein = groot = ceil(sqrt(startgetal)); van te maken

Idd, maar zijn algo klopte wel, ik keek zelf verkeerd.
Ik deed namelijk startgetal - (groot * groot), terwijl ik dat om had moeten draaien

[reddog33hummer]

hey jonges ik keek net ff naar die code van die bigint (java) hoe die deling gaat: dat is een native call.
die gaat dus naar het OS.

[Verwijderd]

Op zondag 04 november 2001 21:42 schreef OiSyN het volgende:
wat probeer je nou eigenlijk te zeggen?
[..]

Natuurlijk zijn 2 en 3 ook priemgetallen, maar denk maar niet dat een van de delers van die RSA getallen onder de 1 miljoen ligt

Wat wil je nou eigenlijk doen? Een lijst van priemgetallen maken of een lijst met priemgetallen die eventueel door de RSA key bedenkers gebruikt zijn? Het eerste is veel eenvoudiger en IMHO ook nuttiger. Je kunt nooit weten!

En kijken of een getal eindigt op 5 heb je gewoon totaal nix aan, omdat je binair zit te rekenen, dus je kunt niet even kijken of het laatste cijfer een 5 is of niet.

Dat is inderdaad waar maar ik denk dat het het waard is de conversie naar base-10 te maken want anders moet je nog ingewikkeldere bewerkingen erop loslaten.

Bovendien zeg je nou dat 5 ook geen priemgetal is, wat dus wel zo is.
Wat je dan eigenlijk zegt is:
[..]

En dan kun je er dus net zo goed bij doen:
Alle getallen deelbaar door 3, behalve 3
Alle getallen deelbaar door 7, behalve 7

En zo kun je nog wel een tijdje doorgaan, en dat is PRECIES wat ik met mijn algoritme doe

Dat bedoelde ik dus niet. Ik was idd vergeten dat ik met mijn regeltje het getal 5 uitsloot. Maar voor de rest klopt het wel, want elk getal eindigend (ik zei niet deelbaar, zoals jij suggereert) op een 5 is ook deelbaar door 5. Dus geen priemgetal!

Dat van die grote getallen die niet normaal deelbaar zijn met simpele instructies op 32 of 64 bits procs: DUH! Als je alle posts had doorgelezen dan had je gelezen dat wij dat al vanaf het begin door hadden, en dat sommige onder ons (waaronder ik) allang weten hoe we dat gaan oplossen.
[..]

Wat een onzin, je kunt toch gewoon je eigen datastructuur definieren en functies maken die daarmee werken? Dan ben je ook klaar, en dit kan in vrijwel elke programmeertaal.

Ik moet dus 260 posts gaan zitten doornemen omdat ik wil helpen? Daar heb ik eigenlijk geen zin in en ik weet ook wel dat als ik iets zeg wat al gezegd is dat ik dat wel te horen zou krijgen. Ik had alleen geen flame verwacht. Bijzonder kinderachtig hoor, als je iemand die probeert te helpen gaat flamen omdat je die persoon niet begrijpt of omdat die persoon beweert dat iets wat jij gezegd hebt niet waar is.

[.oisyn]

is in eerste instantie ook niet erg, maar als je al 20 posts van mensen hebt gehad van mensen die de topic niet helemaal doorlezen dan wordt het behoorlijk irritant, en ja, dan ga ik flamen

Bovendien was jij degene die begon met een flame, en dan doel ik op de laatste alinea van je post. Dat komt over alsof jij denkt dat wij niet door hebben dat we met hele grote getallen aan het werken zijn en dat dat niet zomaar in een normaal datatype past, en dat we dus eigenlijk een stel n00bs zijn die niet weten waar we het over hebben.
En dat kom je dus in deze topic dat fijn even vertellen, zonder eerst de hele thread door te lezen. Dan ben je naar mijn idee zelf verkeerd bezig.

Moet jij eens voorstellen, dat je in een kamertje met wat mensen al een hele tijd loopt te discussieren over een bepaald onderwerp, en dat er dan ineens iemand die kamer binnen loopt, een paar woorden opvangt, en dan gewoon iets zegt wat allang eens eerder aan de orde is geweest. Hoewel het misschien goed bedoeld is schiet de discussie echt totaal niet op als er telkens van die mensen binnen blijven lopen, omdat we op dezelfde punten blijven hangen en steeds telkens opnieuw moeten uitleggen waarom dat wat diegene zei nou wel of niet goed is.

En over dat van die priemgetallen: jij begrijpt totaal mijn doel van die reeks niet, en ik heb geen zin meer om dat nog eens een keer uit te leggen... Ga de hele thread eens lezen zou ik zeggen

.edit: typo

[reddog33hummer]

ff in javacode

[code]
* @param args an array of command-line arguments
*/
public static void main(java.lang.String[] args) {

BigInteger bigInt = new BigInteger("221");//orgineel
BigInteger groot = new BigInteger("15"); //worteltje
BigInteger klein = groot;
BigInteger rest = bigInt.subtract(groot.multiply(groot));

System.gc(); //eerst opruimen!!!

while (rest.signum() != 0) {
if (rest.signum() == 1) {
rest = rest.subtract(klein);
groot = groot.add(BigInteger.ONE);
} else {
rest = rest.add(groot);
klein = klein.subtract(BigInteger.ONE);
}
}
System.out.println(groot);
System.out.println(klein);
}
[\code]

[tomato]

s/\/\//

[.oisyn]

Op maandag 05 november 2001 22:22 schreef tomato het volgende:
s/\/\//

idd, doe er wat aan

[tomato]

tomato: s/\/\//

Oeps, zat nog foutje in:

code:

s/\\/\//

Wat ziet het er toch leuk uit

Of zo natuurlijk:

code:

s{
   \\    # Substitute backslash
 }
 {/}x

* tomato moet even van regexen afblijven en niet meer off-topic gaan

[Killemov]

Ik denk dat we het wiel, of in dit geval de zeef van Eratosthenes, niet opnieuw moeten gaan uitvinden.

- bepaal wat sqrt(BIG) is!
- bepaal wat sqrt(sqrt(BIG)) is!

Even wat processen ...

- Candidate Prime Generator (PCG). Hiervoor heb je 1 computer nodig met een zo groot mogelijke harde schijf. Hoe groter de schijf hoe sneller we door de primespace heengaan. Deze schijf gaat als 'giant wheel' fungeren. Zie de harde schijf (of disk-array) nu eens als een lange array van bitjes. De bitjes waarvan de index een priem is staan op 1, de rest op 0. (Kan gewoon met zeef van Eratosthenes, kost misschien een paar dagen rekenen.) Het aantal bitjes noem ik even N. De index van het laatste bitje van deze bitreeks dat een priem aanduid noemen we Pn. Bij het genereren van Pc's (=kandidaat priemen) > N, kunnen steeds eerder gevonden priemen worden uitgesloten. (bitarray[Pc mod N] == 1 => skip!) Uiteraard zijn bij dit proces processorsnelheid en hoeveelheid geheugen ondergeschikt aan de hoeveelheid diskruimte. Dit proces kan niet worden gedistribueerd. De eerste paar GB van deze bitreeks kan gecomprimeerd op een CD'tje worden gezet. De index van het laatste bitje op deze CD dat een priem aanduid noemen we Pcd.

- Prime Generator (PG). Dit proces bepaalt of een Pc uit de PCG een echte priem is. Alle priemen tot Pn hoeven niet meer te worden geprobeerd, want die zijn al geelimineerd door de PCG. Alle priemen < sqrt(BIG) worden opgeslagen. (Kan dat?) Deze priemen kunnen vervolgens ook weer worden gebruikt voor het verifieren van toekomstige Pc's. Dit rekenwerk kan heel goed worden gedistribueerd. De client krijgt steeds paren van Pc en deler (P(x), dus ook een priem). Het antwoord van de client is dan de restwaarde van Pc mod P(x) (0? => skip!). Om de boel iets te versnellen is het handig om een behoorlijke range (=aantal clients?) van Pc's tegelijk te behandelen. Voorbeeld: 50 clients rekenen voor dezelfde Pc de deler range P(x)..P(x+49) door. Als blijkt dat Pc mod P(x) == 0, dan zijn de berekeningen die gedaan zijn voor P(x+1)..P(x+49) redelijk nutteloos geweest. Je kunt natuurlijk ook pakketten met meer rekenopdrachten versturen. Een vorm van security zou kunnen zijn de berekening van een Pc-deler paar meermaals uit laten voeren op verschillende clients en de resultaten vergelijken.

- Crack Attack generator (CAG). Dit proces genereert alle natuurlijke getallen aflopend van sqrt(BIG) naar sqrt(sqrt(BIG)). (De gezochte priem (Pcw) moet hiertussen zitten!) Dit proces kan niet worden gedistribueerd.

- Crack Attack Quick Eliminator (CAQE). Bepaalt of Pcw uit de CAG deelbaar is door P(1)..P(q). (q is relatief klein, maar groot genoeg om het netwerkverkeer te beperken.) Pcw mod P(x) (0? => skip!) Dit proces kan niet worden gedistribueerd.

- Crack Attack Distributed Eliminator (CADE). Dit proces bepaalt of de Pcw dat door de CAQE is gekomen deelbaar is door P(q+1),P(q+2),P(q+3)..Pcd. Dit proces draait op clients met de eerdergenoemde CD met daarop de bitarray of op clients met de beschikking over een superset van deze bitarray op bijvoorbeeld harde schijf. De index van het laatste bitje van deze superset dat een priem aanduid noemen we Pplus. (Dan wordt er dus berekend van P(q+1) tot Pplus) Het resultaat dat naar de server wordt gestuurd: 0 (het was dus deelbaar door de priemen tot Pcd/Pplus => skip!), Pcd (het was niet deelbaar door priemen tot Pcd) of Pplus (het was niet deelbaar door priemen tot Pplus)

- Crack Attack Distributed Calculator (CADC). Dit proces bepaalt of de Pcw die door de CADE heen is gekomen deelbaar is door priemen uit de priemendatabase. Getest wordt vanaf Pcd of Pplus. Dit proces kan heel goed worden gedistribueerd. Net als bij de PG worden losse rekenopdrachten met paren van Pcw en P(x) naar de cients verstuurd en is het antwoord wederom de restwaarde van Pcw mod P(x).

Er worden dus priemen van laag naar hoog (2..sqrt(sqrt(BIG))) en van hoog naar laag (sqrt(BIG)..sqrt(sqrt(BIG))) uitgerekend. De priemen uit reeks van laag naar hoog worden gebruikt om sneller mogelijke priemen uit de reeks van hoog naar laag te verifieren.

- Crack Attack Attempt. Dit proces gaat vermoedelijke priemen (Pp), ofwel priemen die na een behoorlijke zeefpartij tot P(cmax) nog over zijn gewoon tegen BIG aansmijten. BIG mod Pp == 0? => Gevonden! (Dan nog de andere priem vinden door BIG mod Pp mog een keer uit te voeren en bij te houden hoeveel keer Pp in BIG past.) Dit proces kan ook goed worden gedistribueerd, maar vergt een hogere orde rekenkracht.

De hoofdfunctie die de client heeft is dus het berekenen van de modulus tussen twee big numbers.

Pfff ... morgen weer een dag.

[.oisyn]

waarom moet het getal tussen sqrt (BIG) en sqrt (sqrt (BIG)) zitten? Dat slaat helemaal nergens op...

Als je bijvoorbeeld 194 gaat factorizeren, dan krijg je dus 2 en 97

Geen van deze twee ligt tussen sqrt (194) = 13,928 en sqrt (sqrt (194)) = 3,732

[Verwijderd]

Hier is de source waarmee ze hem hebben gegenereerd (sorry voor de grote lap):

code:

/* Copyright (C) RSA Security,  created 2000.  This is an
   unpublished work protected as such under copyright law.  This work
   contains proprietary, confidential, and trade secret information of
   RSA Security.  Use, disclosure or reproduction without the
   express written authorization of RSA Security is
   prohibited.
 */
/******************************************************************************/
/*
/* Module:      challgen.c
/*
/* Description: Generates and exports moduli from 568 to 2048 bits for the
/*        RSA Factoring Challenge. Uses the BSAFE RSAKeyGen function
/*        and a file of random bytes to create the moduli which are 
/*        then exported in DER format.
/*
/* Syntax:  challgen <EntropyFile> <-d>
/*
/*              Where <EntropyFile> is the name of a binary file containing
/*        at least 31,488 bytes of random data.
/*
/*              Run with -d option to export private key data for testing, not for
/*              actual challenge generation.
/*
/* Output:   Produces  24 files of the form CHALLXXXX.DER where XXXX is
/*        the modulus size, in bits.
/*
/*Revision History:
/*              Created:    2000-04-01 By J. Brainard, RSA Labs
/*
/*Copyright 2000, RSA Security Inc., all rights reserved.
/*
/******************************************************************************/
#include <stdio.h>

#include "aglobal.h"
#include "bsafe.h"

#ifndef TRUE
#define TRUE 1
#define FALSE 0
#endif

#define CHALL_MIN_MODULUS 512+64
#define CHALL_MAX_MODULUS 2048
#define CHALL_MODULUS_INCREMENT 64

/* the public key encryption exponent Fermat 4 (F4) = 65537 */
unsigned char EXPONENT_F4[3] = {0x1, 0x0, 0x1};
B_ALGORITHM_METHOD *CHALLGEN_CHOOSER[] = 
    {
    &AM_SHA_RANDOM,
    &AM_RSA_KEY_GEN,
    (B_ALGORITHM_METHOD *)NULL_PTR
    };

static int bDebugOutput = FALSE;

static B_ALGORITHM_OBJ algCreatePRNG(void);

static int GenerateModulus(const int iModulusSize, B_ALGORITHM_OBJ algPRNG, 
                           FILE *pfilEntropy);

static int SeedPRNG(B_ALGORITHM_OBJ algPRNG, FILE *pfilEntropy, const int iNumBytes);

static unsigned char *aucGenerateKeypair(B_ALGORITHM_OBJ algPRNG, const int iModulusSize, 
                           int *piDERLen);
static int iParseArgs(int argc, char *argv[]);

int main(int argc, char *argv[])
    {   
    FILE *pfilEntropy;

    int iModulusSize, iModuliExported;
    int iReturnCode, iArgsValid;


    B_ALGORITHM_OBJ algPRNG;

    iArgsValid = iParseArgs(argc, argv);
    if (iArgsValid != 0)
        {
        printf("\n\nUsage: challgen EntropyFile [-d]\n\n");
        return(iReturnCode);
        }


    
    /* Open the entropy file. */
    pfilEntropy = fopen(argv[1], "rb");

    if (pfilEntropy == NULL)
        {
        printf("\n\nUnable to open entropy file %s.\n\n");
        return(-2);
        }

    algPRNG = algCreatePRNG();
    if (algPRNG == NULL)
        {
        printf("\n\nError %d creating random number generator object.\n\n");
        return(-3);
        }

    iModuliExported = 0;

    for (iModulusSize = CHALL_MIN_MODULUS;
        iModulusSize <= CHALL_MAX_MODULUS;
        iModulusSize += CHALL_MODULUS_INCREMENT)
        {
        printf("\nGenerating %d bit modulus.\n", iModulusSize);
        iReturnCode = GenerateModulus(iModulusSize, algPRNG, pfilEntropy);
        if (iReturnCode != 0)
            break;
        iModuliExported++;
        }
    
        
    fclose(pfilEntropy);
    B_DestroyAlgorithmObject(&algPRNG);

    if (iModuliExported == ((CHALL_MAX_MODULUS - 
            CHALL_MIN_MODULUS)/CHALL_MODULUS_INCREMENT) + 1)
        printf("\n\nGeneration complete: ");
    else
        printf("\n\nGeneration aborted:  ");

    printf(" %d Moduli Exported.\n\n", iModuliExported);
    return(iReturnCode);
    }

static B_ALGORITHM_OBJ algCreatePRNG(void)
    {
    int iResult;
    B_ALGORITHM_OBJ alg;

    iResult = B_CreateAlgorithmObject(&alg);
    if (iResult != 0)
        return(NULL);
    iResult = B_SetAlgorithmInfo(alg, AI_X962Random_V0, NULL);
    if (iResult != 0)
        return(NULL);
    iResult = B_RandomInit(alg, CHALLGEN_CHOOSER, (A_SURRENDER_CTX *)NULL);
    if (iResult != 0)
        return(NULL);

    return(alg);
    }



static int GenerateModulus(const int iModulusSize, B_ALGORITHM_OBJ algPRNG, 
                           FILE *pfilEntropy)

    {
    char szFN[67];
    FILE *pfOutput;
    unsigned char *aucDER;
    int iDERLen;

    int status;
    unsigned int BytesWritten;
    
    
    /* do {} while(0); provides convenient way to ensure cleanup upon error */
    do {

        /* seed PRNG with a random byte for each bit of the modulus. */
        status = SeedPRNG(algPRNG, pfilEntropy, iModulusSize);
        
        if (status != 0)
            break;
        
    
        aucDER = aucGenerateKeypair(algPRNG, iModulusSize, &iDERLen);
        if (aucDER == NULL)
            {
            status = -1;
            break;
            }

        sprintf(szFN, "CHALL%04d.DER", iModulusSize); 
        pfOutput = fopen(szFN, "wb");
        if (pfOutput == NULL)
            {
            status = -1;
            break;
            }

        

        BytesWritten = fwrite(aucDER, 1, iDERLen, pfOutput);
            
        if (BytesWritten != (unsigned int)(iDERLen & 0x7fff))
            status = -2;
        else
            status = 0;
        
        fclose(pfOutput);       
        T_free(aucDER);
        break;
        }
    while (0);

    return(status);
    }

static int SeedPRNG(B_ALGORITHM_OBJ algPRNG, FILE *pfilEntropy, const int iNumBytes)
    {
    unsigned char *seed;
    int iBytesRead;
    int Status;
    
    do {
        seed = (unsigned char *)T_malloc(iNumBytes);
        if (seed == NULL)
            return(-1);
        iBytesRead = fread(seed, 1, iNumBytes, pfilEntropy);
        if (iBytesRead != iNumBytes)
            {
            fclose(pfilEntropy);
            return(-2);
            }

            

        Status = B_RandomUpdate
              (algPRNG, seed, iNumBytes, (A_SURRENDER_CTX *)NULL_PTR);

        T_free(seed);
        break;
        } while (0);

    
    return(Status);
    }

static int ExportModulus()
    {
    return(0);
    }

static unsigned char *aucGenerateKeypair(B_ALGORITHM_OBJ algPRNG, const int iModulusSize, 
                           int *piDERLen)
    {
    ITEM *keyItemPtrPublic;
    ITEM *keyItemPtrPrivate;

    A_RSA_KEY_GEN_PARAMS keyGenParams;
    B_ALGORITHM_OBJ generateAlgorithmObj = NULL_PTR;
    B_ALGORITHM_OBJ pbEncryptionAlgorithmObj = NULL_PTR;
    B_ALGORITHM_OBJ randomAlgorithmObj = NULL_PTR;
    B_KEY_OBJ privateKeyObj = NULL_PTR;
    B_KEY_OBJ publicKeyObj = NULL_PTR;
    unsigned char *aucOutput;



    int status;
    
                
    do {
        /* create generate algorithm object */
        status = B_CreateAlgorithmObject (&generateAlgorithmObj);
        if (status != 0)
          break;

        /* set up key generation parameters and set algorithm object */
        keyGenParams.modulusBits = iModulusSize;
        keyGenParams.publicExponent.data = EXPONENT_F4;
        keyGenParams.publicExponent.len = sizeof (EXPONENT_F4);
        status = B_SetAlgorithmInfo
          (generateAlgorithmObj, AI_RSAKeyGen, (POINTER)&keyGenParams);
        if (status != 0)
            break;
        /******************************************************************
           NOTE: The choice of F4 (65537) for a public exponent is arbitrary.
           The value 3 or other value may also be used.  See PKCS #1.
         ******************************************************************/

        /* generate init */
        status = B_GenerateInit
          (generateAlgorithmObj,CHALLGEN_CHOOSER,
           (A_SURRENDER_CTX *)NULL_PTR);
        if (status != 0)
          break;

        /* create private and public key objects */
        status = B_CreateKeyObject (&privateKeyObj);
        if (status != 0)
          break;

        status = B_CreateKeyObject (&publicKeyObj);
        if (status != 0)
          break;

        /* generate keys and store in key objects (may take a few moments) */
        status = B_GenerateKeypair
          (generateAlgorithmObj, publicKeyObj, privateKeyObj,
           algPRNG, (A_SURRENDER_CTX *)NULL_PTR);
        if (status != 0)
          break;


        
        if (bDebugOutput == TRUE)
            {
            /* Get private key info, for debug mode only. */
            status = B_GetKeyInfo
                ((POINTER *)&keyItemPtrPrivate, privateKeyObj, KI_PKCS_RSAPrivateBER);
            if (status != 0)
                break;
            *piDERLen = keyItemPtrPrivate->len; 
            }
        else
            {
            /* request the Distinguished Encoding (DER) of the public key
            (see PKCS #1) and store it in the supplied buffer */
            status = B_GetKeyInfo
            ((POINTER *)&keyItemPtrPublic, publicKeyObj, KI_RSAPublicBER);
            if (status != 0)
            break;
            *piDERLen = keyItemPtrPublic->len;
            }

        aucOutput = (unsigned char *)(T_malloc(*piDERLen));
        if (aucOutput == NULL)
            break;
        
        if (bDebugOutput == TRUE)
            {
            /* Write out the private key DER in debug mode. */
            T_memcpy(aucOutput, keyItemPtrPrivate->data, keyItemPtrPrivate->len);
            }
        else
            {   
            /* Write out the public key DER. */
            T_memcpy(aucOutput, keyItemPtrPublic->data, keyItemPtrPublic->len);
            }
        } while (0);
    
    B_DestroyKeyObject(&privateKeyObj);
    B_DestroyKeyObject(&publicKeyObj);
    B_DestroyAlgorithmObject(&generateAlgorithmObj);
    return(aucOutput);
    }


static int iParseArgs(int argc, char *argv[])
    {
    if ((argc < 2) || (argc > 3))
        return(-1);
    
    bDebugOutput = FALSE;

    if (argc == 3)
        {
        if (argv[2][0] != '-')
            return(-2);
        
        switch(argv[2][1])
            {
            case 'd':
            case 'D':
                bDebugOutput = TRUE;
                break;

            default:
                return(-3);

            }   
        }
    return(0);
    }

[Verwijderd]

Toch nog ff twee hints


• De RSA-code is een factor van exact twee priemen. Om te voorkomen dat de eerste de beste jan-met-de-korte-achternaam die code meteen kraakt, zal niet een van de priemen ontzettend klein zijn en de andere ontzettend groot, maar ze zullen ook niet alletwee ongeveer even groot (rond sqrt(code)) zijn. Anders kun je namelijk een simpel 20-regelig programmaatje schrijven dat het oplost.
• Er zijn snelle algoritmes om te bepalen of een getal priem is of niet (veel sneller dan proefdeling). De zeef van Erathostenes is dan weliswaar de snelste methode om kleine priemen te genereren; zodra je disks gaat gebruiken om dat bit-array op te slaan loopt de snelheid drastisch terug. Dan is het beter een groot getal te genereren en met een snelle test te kijken of het een priem is; dan spinnen je disks niet zo en dat werkt een stuk sneller.

[Verwijderd]

Op dinsdag 06 november 2001 00:32 schreef mietje het volgende:
[...]
Dan is het beter een groot getal te genereren en met een snelle test te kijken of het een priem is;
[...]

Agreed...

[htca]

Bijna helemaal mee eens.
De kans dat het getal inderdaad tussen sqrt(BIG) en sqrt(sqrt(big)) zit is groter dan dat het tussen 0 en sqrt(sqrt(big)) zit.
Let wel, het blijft een kans. Je skipt dus bewust een deel van de oplossingsruimte. Om het helemaal correct doet kun je vanaf sqrt(BIG) naar beneden toe beginnen te zoeken. De kans is groot dat je voor sqrt(sqrt(big)) de eerste priem hebt gevonden en daarmee automatisch de tweede.
Als je de oplossingen verkleind door de veelvouden van 2,3 en 5 skipt (relatief gemakkelijk te checken) houd je de getallen onder sqrt(BIG) nog maar 8.33% (1/12 deel) over.

[Verwijderd]

Op dinsdag 06 november 2001 00:32 schreef mietje het volgende:

• De RSA-code is een factor van exact twee priemen. Om te voorkomen dat de eerste de beste jan-met-de-korte-achternaam die code meteen kraakt, zal niet een van de priemen ontzettend klein zijn en de andere ontzettend groot, maar ze zullen ook niet alletwee ongeveer even groot (rond sqrt(code)) zijn. Anders kun je namelijk een simpel 20-regelig programmaatje schrijven dat het oplost.

Ze zijn wel ongeveer evengroot omdat beide priemen uit evenveel bits bestaan.(het bewijs hiervan heb ik niet in de sourcecode kunnen vinden(die KixAss456 heeft opgevaargd )maar bij alle opgeloste rsa getallen is dat zo)
bijv. de 576 bits rsa bestaat uit 2 priemen van 288 bits
dus de kleinste priem zit tussen de sqrt(rsa_174) en rsa_174/(2^289-1) dat betekent dat je maar op 2.446607...*10^86 getallen hoeft te zoeken dat is iets meer dan de helft van sqrt(rsa_174). Zouden de priemen niet evengroot zijn dan zou je maar minder dan half wortel rsa-getal getallen hoeven te controleren (nog een bewijs dat de priemen van de rsa-getallen evengroot zijn in bits)

[Verwijderd]

Op dinsdag 06 november 2001 09:29 schreef borganism het volgende:

[..]

Ze zijn wel ongeveer evengroot omdat beide priemen uit evenveel bits bestaan.(het bewijs hiervan heb ik niet in de sourcecode kunnen vinden(die KixAss456 heeft opgevaargd )maar bij alle opgeloste rsa getallen is dat zo)
bijv. de 576 bits rsa bestaat uit 2 priemen van 288 bits
dus de kleinste priem zit tussen de sqrt(rsa_174) en rsa_174/(2^289-1) dat betekent dat je maar op 2.446607...*10^86 getallen hoeft te zoeken dat is iets meer dan de helft van sqrt(rsa_174). Zouden de priemen niet evengroot zijn dan zou je maar minder dan half wortel rsa-getal getallen hoeven te controleren (nog een bewijs dat de priemen van de rsa-getallen evengroot zijn in bits)

De eerste bit van die code is automatisch 1, anders heb je in plaats van een 1024 bits getal (bij de 2048 bits chalange) een 1023 bits getal. Iig als die getallen echt even groot zijn (in lengte dan), dan is het veel sneller om het verschil uit te rekenen.
[refreshing memory mode]
p1 > p2
code = p1*p2
g = (p1+p2)/2
d = p1-g = g-p2 dus g+d = p1 en g-d = p2
sqrt(code+(d^2))=g

Uit een "random" d is g te berekenen, en dus p1 en p2.
[/refreshing memory mode]
Als je voor d de waarden 0 tot 1000 neemt, heb je al afstanden van 2.000.000 gechecked. ((d^2)*2)

[htca]

Als je ervan uitgaat dat de priemen even lang zijn (in characters), ik heb het ook niet in de code kunnen vinden overigens, dan is de wortel van het getal nog steeds het uitgangspunt.
Stel in het geval van RSA-576 de wortel wordt benaderd op 4.3381887115E+86, dat betekend simpel (nou ja simpel), dat de priemen in de range zitten:
1.0000000E+86 en 9.999999E+86

Omdat als je een priem hebt gevonden, de andere dus ook automatisch hebt. Waarbij je ervan uit kunt gaan dat er een boven en een onder de wortel ligt. Hoef je 'slechts' te zoeken (in dit geval) tussen 1E+86 en 4.3381887115E+86.

Dit alles ervan uitgaande dat de priemen even lang zijn in karakters.

iemand anders nog andere denkwijzen in het verkleinen van de oplossingsruimte?

[Verwijderd]

Dat is dan afgerond nog 9E+86.

Dat is met 1000 pc's en 85% not-prime-skip en 1000 keys per seconde nog:

*rekenreken*


4.3E+72 jaar. Ook al zijn je variabelen gunstiger, (meer pc's ec.) dan nog doe je er relatief erg lang over lijkt me.

[Verwijderd]

Op dinsdag 06 november 2001 12:03 schreef htca het volgende:
Als je ervan uitgaat dat de priemen even lang zijn (in characters), ik heb het ook niet in de code kunnen vinden overigens, dan is de wortel van het getal nog steeds het uitgangspunt.
Stel in het geval van RSA-576 de wortel wordt benaderd op 4.3381887115E+86, dat betekend simpel (nou ja simpel), dat de priemen in de range zitten:
1.0000000E+86 en 9.999999E+86

Het is evenlang in bits dus de range is 2^287 tot (2^288)-1 en dat is ongeveer 2.486616E+86 tot 4.973232E+86 en verder is de kleinste priem altijd groter dan rsa_174/(2^288) = 3.784235E+86 en kleiner dan de wortel.zodat de werkelijk zoekrange ligt tussen ongeveer 3.784235E+86 en 4.3381887E+86 dat is een zoekrange van 'slechts' 5.539534E+85

[paknaald]

priem * priem = ....9
priem1 eindigt op 1, priem2 eindigt op 9 OF
priem1 en priem2 eindigen op 3.

kweet niet of dat al in de methode verwerkt zit maar het bespaart wel 80% (in het geval van 9) en 46% rekenkundig gemiddeld voor 0 t/m 9.

geen wiskundig genie hier maar ja, stel da gullie er iets aan hebben

[htca]

Op dinsdag 06 november 2001 12:28 schreef paknaald het volgende:
priem * priem = ....9
priem1 eindigt op 1, priem2 eindigt op 9 OF
priem1 en priem2 eindigen op 3.

kweet niet of dat al in de methode verwerkt zit maar het bespaart wel 80% (in het geval van 9) en 46% rekenkundig gemiddeld voor 0 t/m 9.

geen wiskundig genie hier maar ja, stel da gullie er iets aan hebben

OF:
priem1 eindigt op 7 en priem2 eindigt op 7 (7*7=49).
Dus alle getallen eindigend op een oneven cijfer (behalve 5).