[All language] Programmeer webstrijd

[Anoniem: 23074]

Oke, een beetje denkend aan [topic=305909/1/100] lijkt het me wel leuk, om daarover te overleggen, maar ik zal eerst ff de situatie uitleggen...

RSA Security heeft op haar website, een wedstrijd neergezet, over het hacken van een code:

25195908475657893494027183240048398571429282126204
03202777713783604366202070759555626401852588078440
69182906412495150821892985591491761845028084891200
72844992687392807287776735971418347270261896375014
97182469116507761337985909570009733045974880842840
17974291006424586918171951187461215151726546322822
16869987549182422433637259085141865462043576798423
38718477444792073993423658482382428119816381501067
48104516603773060562016196762561338441436038339044
14952634432190114657544454178424020924616515723350
77870774981712577246796292638635637328991215483143
81678998850404453640235273819513786365643912120103
97122822120720357

Wat moet er gebeuren

Je hebt een groot getal (zoals hier boven staat). Daaruit, moeten 2 priemgetalen worden berekend, die, als je de product er van pakt (de ene X de andere), dat getal als uitkomst moeten hebben...

Voorbeeld:

Opgave:
Je hebt de uitkomst: 26
dan is de som: X * Y = 26
X en Y zijn priemgetallen

De vraag is, wat zijn X en Y

Antwoord:
X = 2
Y = 13

Wat als idee naar voren is gekomen _{(C) OiSyN}:

laten we zelf een distributed systeem bouwen onder alle GoT'ers en tweakers, we berekenen de getallen en we verdelen het geld onder de deelnemers

Dus, post hier je ideen, mening etc hierover...

[Anoniem: 12353]

Is dit niet de zelfde code die die dpc lui aan het kraken zijn?

[Anoniem: 23074]

Nope, dit != RC5, maar mischien heeft et er wel mee te maken

* Anoniem: 32243 pakt ff de DPC Sourcecode erbij

[JeroenB]

Dit is gewoon standaard RSA-theorie. Veel success met het kraken Ik denk dat je beter heel DPC hiervoor kunt mobiliseren.

[Gerco]

Op woensdag 31 oktober 2001 12:33 schreef KixAss456 het volgende:
Je hebt een groot getal (zoals hier boven staat). Daaruit, moeten 2 priemgetalen worden berekend, die, als je de som er van pakt (de ene X de andere), dat getal als uitkomst moeten hebben...

[mierenneukmode]
het produkt !
[/mierenneukmode]

[Anoniem: 23074]

Op woensdag 31 oktober 2001 12:43 schreef Gerco het volgende:

[..]

[mierenneukmode]
het produkt !
[/mierenneukmode]

dat was hem, ik was hem ff kwijt, het lag op het puntje van m'n keyboard...

[tus]

Ik kan niet eens voorstellen hoe groot dat getal is in guldens... Laat staan uitrekenen welke 2 priemgetallen hier bij horen.

Het moet in ieder geval met n snelle programmeertaal gedaan worden. Dus VB kunnen we schrappen.

Hoe maak je trouwens n distributed app? Lijkt me niet zo simpel.

Ik begin er in ieder geval niet aan. Duurt mij te lang eer je het gevonden hebt

[mbravenboer]

Ach, dat zie je toch zo .

[Anoniem: 23074]

Op woensdag 31 oktober 2001 12:47 schreef Tus het volgende:
Ik kan niet eens voorstellen hoe groot dat getal is in guldens... Laat staan uitrekenen welke 2 priemgetallen hier bij horen.

Bankrekening van Bill Gates

Het moet in ieder geval met n snelle programmeertaal gedaan worden. Dus VB kunnen we schrappen.

VB is in het rekenen, ongeveer net zo snel als C++, VB is in schermopbouw en event handling gewoon langzamer...

Hoe maak je trouwens n distributed app? Lijkt me niet zo simpel.

Je maakt een proggie, die rekent gewoon uit, van hier tot daar, ligt eraan van wat ie doorkrijgt

Ik begin er in ieder geval niet aan. Duurt mij te lang eer je het gevonden hebt

[Anoniem: 10867]

geinig idee.

[Anoniem: 37406]

Hrm, had ff geprobeerd in miranda (functioneel, lekker snel) maar die kan niet zulke lange getallen

[Anoniem: 3652]

hmm. een getal van meer dan 600 tekens crunchen om er 2 priemgetallen uit te halen. met een 64 bits getal kom je er nog niet aan. dus zul je zelf iets moeten verzinnen om met zo'n grote getallen te werken.

Distributed klinkt leuk, maar ik denk dat het verstandig is om eerst eens over het algoritme na te denken. Dit is misschien daar wel een idee voor:
code = dat getal van 600+ cijfers.
priem1 = het eerste priemgetal, het getal wat je nu aan het crunchen bent.
code % priem1 (java) moet 0 opleveren.
code/priem1 = priem2 = het 2e priemgetal.

[marcusk]

Op woensdag 31 oktober 2001 12:51 schreef KixAss456 het volgende:
VB is in het rekenen, ongeveer net zo snel als C++, VB is in schermopbouw en event handling gewoon langzamer...

veel succes met de assable assembly-code dan

Je maakt een proggie, die rekent gewoon uit, van hier tot daar, ligt eraan van wat ie doorkrijgt

jij hebt dit zeker nog niet gelezen. Ze lofen echt geen $10.000 weg als je 'zo ff doet' hoor

[Anoniem: 23074]

Op woensdag 31 oktober 2001 13:10 schreef GHOst. het volgende:
hmm. een getal van meer dan 600 tekens crunchen om er 2 priemgetallen uit te halen. met een 64 bits getal kom je er nog niet aan. dus zul je zelf iets moeten verzinnen om met zo'n grote getallen te werken.

Distributed klinkt leuk, maar ik denk dat het verstandig is om eerst eens over het algoritme na te denken. Dit is misschien daar wel een idee voor:
code = dat getal van 600+ cijfers.
priem1 = het eerste priemgetal, het getal wat je nu aan het crunchen bent.
code % priem1 (java) moet 0 opleveren.
code/priem1 = priem2 = het 2e priemgetal.

in VB:
If code Mod priem = 0 Then

[mbravenboer]

fladder: Hrm, had ff geprobeerd in miranda (functioneel, lekker snel) maar die kan niet zulke lange getallen

Over het algemeen is functioneel (helaas) nog absoluut niet synoniem met snel hoor! Functionele talen programmeren extreem snel omdat ze zo declaratief zijn, maar vanwege deze declaratieve aanpak kunnen ze toch vaak niet op tegen imperatieve implementaties .

[Gerco]

Op woensdag 31 oktober 2001 13:12 schreef KixAss456 het volgende:
in VB:
If code Mod priem = 0 Then

En dat gaat lukken met een getal van een paar honderd cijfers?

Trouwens... ik denk dat als je in VB met strings gaat werken, C++ met zijn char* wel IETS vlugger is. Daar zit al die management zooi van COM BSTR's niet achter en in VB wel.

[marcusk]

Op woensdag 31 oktober 2001 13:15 schreef Gerco het volgende:
Trouwens... ik denk dat als je in VB met strings gaat werken, C++ met zijn char* wel IETS vlugger is. Daar zit al die management zooi van COM BSTR's niet achter en in VB wel.

Als je dit serieus wilt doen gaan je zowiezo niet met strings werken

[Anoniem: 23074]

Op woensdag 31 oktober 2001 13:15 schreef Gerco het volgende:

[..]



En dat gaat lukken met een getal van een paar honderd cijfers?

Trouwens... ik denk dat als je in VB met strings gaat werken, C++ met zijn char* wel IETS vlugger is. Daar zit al die management zooi van COM BSTR's niet achter en in VB wel.

Jep, maar daar gaat het nog niet om, eerst ff kijken _hoe_ we het gaan doen...
Daarna, komt pas de taal ed.

[raptorix]

Iemand goed in hoofdrekene

[Anoniem: 23074]

Op woensdag 31 oktober 2001 13:20 schreef raptorix het volgende:
Iemand goed in hoofdrekene

Ik ken iemand, die heeft Pi om 50 decimalen achter de komma, uit z'n hoofd, uitgerekend, daar heb ik het ook al ff naar gemeeld, ik w8 op zijn reactie...

[wasigh]

Op woensdag 31 oktober 2001 13:20 schreef raptorix het volgende:
Iemand goed in hoofdrekene

Daar heb ik een pc voor

[raptorix]

FF snel gedacht ik heb hier niet zo veel ervaring in, maar is het niet zo dat het handig is om eerste alle priemgetallen uit te rekenen tot dat getal? Als je die allemaal hebt dan maakt het het distributed verhaal in ieder geval makkelijker.

[rjsomeone]

Ik denk dat dit heel simpel te maken is:

Je maakt een cgi script dat een op een bepaalde server draait (t.net ? ), dat 2 bestanden bewaart: ten eerste een getal met waar hij gebleven is met uitgeven van getallen, ten tweede een bestand met alle pakketjes die nog niet terug gekomen zijn.

Voorbeeldje(onder de 20):
iemand haalt bij 't cgi script 1 pakketje op, met daarin 5 getallen:
1
2
3
4
5
de cgi onthoudt dan 't getal 6, zodat als de volgende een pakketje komt ophalen, diegene 6,7,8,9,10 meekrijgt.
Als 't paketje met 1 tm 5 erin is opgehaald, schrijft de server in dat andere bestand het getal 1, zodat hij weet dat 1 (tm 5) uitgeleend is. Als pakketje 1 weer (uitgerekend) wordt ingeleverd wordt het getal 1 verwijderd uit de uitgeleende lijst.

Nu moet er een programmaatje bij geschreven worden dat gewoon die website(cgi dus) uitleest en met variabelen post. Kortom een programmaatje dat kan communiceren met die cgi site. (Heb ik wel in VB). Dat programma moet ook kunnen rekenen met die getallen, hij moet het rsa getal delen door alle getallen uit 't pakketje en als daar een heel getal uitkomt moet hij dat melden aan de cgi site, dan heb je 't getal gevonden en de $ binnen.

Ik hoop dat 't een beetje duidelijk is.. Ik wil 't programma wel schrijven in vb, want zo langzaam is dat niet volgens mij. Als jullie even aangeven of dat ok is, dan begin ik er vandaag nog aan.. Als vb niet handig is, zal iemand anders 't moeten schrijven, maar de cgi wil ik ook wel doen...

[Anoniem: 3652]

ok. volgens mij heb je 2 algoritmes nodig. het eerste wat alle priemgetallen tot code/2 uitrekend, en het tweede wat conmtroleerd of een van die priemgetallen de juiste is. Het probleem is alleen, je hebt een fokking grote schijf nodig om al die getallen op te slaan!

[HurrI]

Op woensdag 31 oktober 2001 13:25 schreef raptorix het volgende:
FF snel gedacht ik heb hier niet zo veel ervaring in, maar is het niet zo dat het handig is om eerste alle priemgetallen uit te rekenen tot dat getal? Als je die allemaal hebt dan maakt het het distributed verhaal in ieder geval makkelijker.

Alle priemgetallen tot de wortel van dat getal scheelt weer...

[mbravenboer]

Ik vind jeugdig enthousiasme prachtig, maar zie hier nu toch vrij veel onzin... Bij dergelijke problemen gaat het allereerst niet om de taal of technieken die je gebruikt (hoe interessant dat ook is). Dit probleem heeft een bepaalde complexiteit en wat je ook uit de kast trekt, daar ontkom je niet aan. De complexiteit van dit probleem is zo enorm dat er een ongelofelijke hoeveelheid rekenkracht voor nodig is. Die moet gewoon geleverd worden (maar is niet echt beschikbaar). Allerlei technieken, talen en data-typen veranderen daar helemaal niets aan.... Hooguit kan de benodigde tijd met een constante worden verminderd.

[rjsomeone]

Op woensdag 31 oktober 2001 13:25 schreef raptorix het volgende:
FF snel gedacht ik heb hier niet zo veel ervaring in, maar is het niet zo dat het handig is om eerste alle priemgetallen uit te rekenen tot dat getal?

Ik denk 't niet, om al die priemgetallen uit te rekenen ben je nog veel langer bezig (.. je kan beter alle getallen proberen, heb je 't juiste getal is 't automatisch een priemgetal.)

[HurrI]

Op woensdag 31 oktober 2001 13:33 schreef rjsomeone het volgende:

[..]

Ik denk 't niet, om al die priemgetallen uit te rekenen ben je nog veel langer bezig (.. je kan beter alle getallen proberen, heb je 't juiste getal is 't automatisch een priemgetal.)

In orde van grote van priemgetallen waar je op uitkomt is het aantal priem tov niet priem zo weinig dat het wel degelijk sneller is om eerst een verzameling priemgetallen te maken. En vervolgens verder rekenen met deze verzameling

[raptorix]

Plus dat je de priemgetallen weer kan her gebruiken voor de andere wedstrijdjes

[HurrI]

Een quotje uit tentamen stof:

3.2Priemgetallen

Een natuurlijk getal n heet een priemgetal, als n > 1 en n heeft maar twee positieve delers, n.l. 1 en n zelf.
Een getal, dat niet een priemgetal is heet samengesteld (composite).
Je kunt een lijst van priemgetallen b.v. kleiner dan 100 maken, m.b.v. de z.g. zeef van Eratosthenes. Dat gaat als volgt:

·Schrijf de getallen 2 t/m 100 op (1 is geen priemgetal).
·het eerste getal is 2, verwijder alle veelvouden van 2 behalve 2 zelf
·het volgende getal is 3, verwijder alle veelvouden van 3, behalve 3 zelf
·het volgende getal is 5, verwijder alle veelvouden van 5, behalve 5 zelf
·enz. totdat het volgende getal groter is dan = 10.

[joepP]

Leuk maar onmogelijk. Helaas....

De RSA is de grootste werkgever van wiskundigen TER WERELD. Met een belachelijk groot budget. Deze luitjes doen zeer veel research naar beveiligingen, waaronder RSA. Reken er dus maar never nooit niet op dat jullie hier 'eventjes' een progje maken dat dit oplost. Ook niet distributed.

De enige kans ligt misschien in het ontdekken van zwakheden in hun priemgenerator. Maar reken er maar niet op dat je die vindt.

Enne... voor dit probleem heb je geen programmeurs nodig, maar wiskundigen.

[rjsomeone]

Op woensdag 31 oktober 2001 13:36 schreef HurrI het volgende:

[..]

In orde van grote van priemgetallen waar je op uitkomt is het aantal priem tov niet priem zo weinig dat het wel degelijk sneller is om eerst een verzameling priemgetallen te maken. En vervolgens verder rekenen met deze verzameling

Duurt het niet heel lang om al die priemgetallen uit te rekenen? In vb (en zeg niet weer dat vb traag is ) duurt 't bijv bij mijn programma (een snel algoritme) 3 sec om de 1e 10000 uit te rekenen. de 1e 100000 doet ie ong 50 sec over dus ong 17x zo lang, reken maar uit hoelang 't dan duurt om alle getallen tot 100 tekens lang uit te rekenen.

[Tieske|IA]

Eerst de wortel pakken van het grote getal. Dan kan je zowieso al alle vermenigvuldigingen van de getallen onder die wortel met elkaar al wegstrepen. Als het getal 23 is, is de wortel 4,80 ongeveer. Alle combinaties van priemgetallen onder de 4 vallen dus weg. (1*1, 1*2, 1*3, 2*1, 2*2, 2*3, 3*1, 3*2, 3*3). Die hoef je dus al niet meer uit te rekenen, dat scheelt al een hele hoop. Dat kan je ook doen met een groot gedeelte aan berekeningen die boven dat wortelgetal zitten, dus 7*7, 7*11 en dat soort dingen, want de uitkomst is zowieso te hoog.

Dat domein waar je overhoud, daar moet je in zoeken dan. Hoe? Even denk...

edit: Alle combinaties van niet-priemgetallen vanaf tot aan het wortelgetal vallen ook weg. Mocht je toch eerst alle priemgetallen willen uitrekenen, kun je die ook weglaten.

[rjsomeone]

Op woensdag 31 oktober 2001 13:40 schreef joepP het volgende:
Leuk maar onmogelijk. Helaas....

Niets is onmogelijk, het zal wel een tijdje duren, maar d.net krijgt 't toch ook veel elkaar om wat van dit soort dingen te kraken? Waarom wij niet.. misschien moeten we 't iets groter aan pakken (wat meer mensen die 't programma draaien, maar de techniek is goed, en het is op onze manier oplosbaar, 't duurt alleen een tijdje )

[mbravenboer]

Tieske: Alle combinaties van priemgetallen onder de 4 vallen dus weg. Die hoef je dus al niet meer uit te rekenen, dat scheelt al een hele hoop.

Sorry hoor, maar lees nou eens dat getal op wat er staat...

Enig besef van orde van grootte is hier wel op z'n plaats. Leuk idee, maar niet te realiseren door amateurs als wij met weinig organisatorische en technische mogelijkheden. Er zijn slechts enkele organisaties (alleen de RSA wellicht) die dit brute-force zouden kunnen kraken.

[Anoniem: 3652]

een ideetje voor de code. De code zelf zit vol bugs, dus moet je het zelf even goed werkend krijgen, maar het idee is er.

code:

String code = "<code>";
String priem1 = "<crunch>";

// code en priem zelfde lengte maken 
String priem;
int i = code.length - priem1.length;
for (int j = 0; j < i; j++)
{
    priem += "0";
}
priem += priem1;

//een keer priem1 van code af halen:
for (int i = priem.length; i >= 0; i--)
{
    int c = Integer(code.charAt(i)).intValue();
    int p = Integer(priem.charAt(i)).intValue();
    int uitkomst = c - p;
    if (uitkomst < 0)
    {
        herstelCode();
        uitkomst += 10;
    }
    c.charAt(i) = uitkomst;
}

herstelCode:
hier word een gedeelte van het getal wat onder 0 komt omgerekend zodat het weer boven 0 komt.
Bijvoorbeeld:
C = 2
P = 4
getal voor C in code = 5.

Deze code zorgt ervoor dat C 12 word, en het getal voor C in code 4.

[Tieske|IA]

Natuurlijk is het getal veel groter. Maar de te boeken winst met het wegstrepen van combinaties is ook groter. Bij een getal van bijvoorbeeld 10000, vallen alle combinaties van getallen tot aan 100 weg. 99 tot de 99e berekingen minder. Of ben ik gek? 1 x [alle getallen t/m 99] + 2 x [alle getallen t/m 99] zoveel vallen d'r weg. Das niet niks.

[Anoniem: 7477]

Op woensdag 31 oktober 2001 13:43 schreef Tieske het volgende:
Eerst de wortel pakken van het grote getal. Dan kan je zowieso al alle vermenigvuldigingen van de getallen onder die wortel met elkaar al wegstrepen. Als het getal 23 is, is de wortel 4,80 ongeveer. Alle combinaties van priemgetallen onder de 4 vallen dus weg. (1*1, 1*2, 1*3, 2*1, 2*2, 2*3, 3*1, 3*2, 3*3). Die hoef je dus al niet meer uit te rekenen, dat scheelt al een hele hoop. Dat kan je ook doen met een groot gedeelte aan berekeningen die boven dat wortelgetal zitten, dus 7*7, 7*11 en dat soort dingen, want de uitkomst is zowieso te hoog.

Dat domein waar je overhoud, daar moet je in zoeken dan. Hoe? Even denk...

edit: Alle combinaties van niet-priemgetallen vanaf tot aan het wortelgetal vallen ook weg. Mocht je toch eerst alle priemgetallen willen uitrekenen, kun je die ook weglaten.

Oftewel een priem van onder de wortel maal een priem van boven de wortel.

En aangezien elk probleem is op te lossen als je het maar in kleine stapjes opdeelt heb ik hier stap 1.

Het uitrekenen van de wortel van ons mooie getal. Veel plezier.

[Anoniem: 23074]

Op woensdag 31 oktober 2001 13:49 schreef GHOst. het volgende:
een ideetje voor de code. De code zelf zit vol bugs, dus moet je het zelf even goed werkend krijgen, maar het idee is er.

code:

String code = "<code>";
String priem1 = "<crunch>";

// code en priem zelfde lengte maken 
String priem;
int i = code.length - priem1.length;
for (int j = 0; j < i; j++)
{
    priem += "0";
}
priem += priem1;

//een keer priem1 van code af halen:
for (int i = priem.length; i >= 0; i--)
{
    int c = Integer(code.charAt(i)).intValue();
    int p = Integer(priem.charAt(i)).intValue();
    int uitkomst = c - p;
    if (uitkomst < 0)
    {
        herstelCode();
        uitkomst += 10;
    }
    c.charAt(i) = uitkomst;
}

herstelCode:
hier word een gedeelte van het getal wat onder 0 komt omgerekend zodat het weer boven 0 komt.
Bijvoorbeeld:
C = 2
P = 4
getal voor C in code = 5.

Deze code zorgt ervoor dat C 12 word, en het getal voor C in code 4.

kun je ff in NL vertalen, wat het doet, ik ken amper JScript, dus...

[rjsomeone]

Op woensdag 31 oktober 2001 13:59 schreef KixAss456 het volgende:

[..]

kun je ff in NL vertalen, wat het doet, ik ken amper JScript, dus...

of in VB

[Anoniem: 23074]

Op woensdag 31 oktober 2001 14:00 schreef rjsomeone het volgende:

[..]

of in VB

ook goed

[Anoniem: 3652]

Op woensdag 31 oktober 2001 13:59 schreef KixAss456 het volgende:

[..]

kun je ff in NL vertalen, wat het doet, ik ken amper JScript, dus...

ok. maak een array van karakters van de code en het priemgetal. Deze arrays moeten even groot zijn, dus moet aan het begin van het priem array een aantal keer 0 staan.

Dan ga je priem van code af halen.
pak het achterste karakter van priem, en haal die van het achterste karakter van code af. Indien je dan onder de 0 komt, moet je even zorgen dat je weer boven de 0 uit komt door van het volgende karakter 1 af te halen.

Ik heb denk ik een manier bedacht waarop de code veel sneller word, maar voordat ik die serieus uit ga werken wil ik eerst weten of we dit dingetje nou echt gaan bouwen...

[Anoniem: 23074]

Ik snap het nog steeds niet egt, maar dat zal wel aan mij liggen

Maaruh, ik ben zeker wel van plan (als het te doen is) om het te bouwen/kraken, nog niet eens om het geld, maar gewoon als Tweakers.net

edit:

Mischien wel een leuk idee, al het geld wat we winnen, gaat naar Tnet

[Anoniem: 3652]

hmm. dan zal ik het nog een keer uit proberen te leggen.
code = 25
priem = 3

code:

[2][5] (code)
[0][3] (priem)
-------
[2][2] (nieuwe code)
[0][3] (priem)
-------
[2][-1] (nieuwe code voor correctie)
[1][9] (nieuwe code na correctie)

beter?

[Anoniem: 23074]

Ik moet het ff laten zakken M'n hele hoofd zit wol met verschillende manieren te bedenken, dus gaat alles door mekaar heen...

[Anoniem: 37406]

Voordat je allerlei "oplossingen" bedenkt die al die mensen die hier al jaren over nadenken al lang weer aan de kant hebben geschoven, lees dit ook ff:

http://www.rsasecurity.com/rsalabs/challenges/factoring/faq.html#WhatAreTheBest

[rjsomeone]

Ja, ik snap 't, delen is gewoon herhaaldelijk aftrekken..
Ik ben ook wel van plan hier een (distributed) programma van te maken.

[Anoniem: 7477]

Op woensdag 31 oktober 2001 14:25 schreef fladder het volgende:
Voordat je allerlei "oplossingen" bedenkt die al die mensen die hier al jaren over nadenken al lang weer aan de kant hebben geschoven, lees dit ook ff:

http://www.rsasecurity.com/rsalabs/challenges/factoring/faq.html#WhatAreTheBest

Ja maar het is leuk erover te denken. Ook al is dat al eerder door slimmere mensen gedaan.

Ik heb net effe m'n eerste zeef gebouwd. Op een sap systeem (lekkere zware server hier) een abapje. Helaas is het maximum beperkt tot 2147483647, hierboven kan ik niet meer van integers gebruik maken in deze progtaal. En ik ben te lui om het anders te gaan verzinnen, ik moet tenslotte ook gewoon werken.

(eens kijken de alle priemen onder de 1000000, eeuh dat zijn er (8,3 sec gewacht ) 78.498 Lekkere server hier

[rjsomeone]

en hoelang doet ie over de 1e 10000000?
is dat ong. een factor 10 langer ? Zo ja, dan gaat 't volgens mij te langzaam.

[rjsomeone]

Ok, even een korte samenvatting(zoals ik 't zie):

1. Er moet algoritme komen dat hele lange getallen kan delen.
2. Dat algoritme moet in een programma gezet worden, dat kan communiceren met een cgi script.
3. Er moet een algoritme komen voor een cgi script dat kan tellen tot een getal van 100 zoveel cijfers.
4. Een cgi script.

Volgens mij is 1 't lastigst.

Gaan we dit doen, en zo ja wie doet wat? Ik kan denk ik bij alle 4 wel helpen, mits het in vb of cgi is.

[Anoniem: 3652]

hmm. als we nou eens beginnen met de eerste, die van 174 tekens...

[Anoniem: 37406]

Eer vanuit gaande dat we het hebben over het kleinste getal op die site (174 digits) is de wortel ongeveer

4339 * 10^83

edit:

nauwkeuriger:
4338188711 * 10^77

best groot wel

[Anoniem: 7477]

Op woensdag 31 oktober 2001 14:39 schreef rjsomeone het volgende:
en hoelang doet ie over de 1e 10000000?
is dat ong. een factor 10 langer ? Zo ja, dan gaat 't volgens mij te langzaam.

Yep, 90,79 secs. Maare dit was niet bedoelt als oplossing hoor, slechts om de priemgetallen te bepalen tot de helft van het getal. Enne daar gebruik je geen erp pakket voor hoor.

Eens kijken, voor alle priems tot 600 cijfers geeft dat dus (vooropgesteld dat ik met zeer grote getallen even efficient kan rekenen met die waar ik nu mee reken (not)) eeeuh ongeveer 15 uur stevig stampen.

Tja, thuis maar eens een poging gaan doen om dit voor grotere getallen te laten gebeuren. Nu nog het probleem oplossen dat ik geen computijd heb voor dit soort berekeningen. Trouwens voor de rest zit ik ook met vriendin, dochter en nieuw huis, hmm ik geef het stokje weer over hoor.

[ronaldmathies]

Hier is een klein stukje wat ik heb kunnen vinden over het bepalen of een priem getal een priem getal is.

Ik ga vanavond eens kijken of ik wat kan bedenken om één computer te laten rekenen. (Nog niet distributed) maar het lijkt mij een leuke uitdaging om te kijken of en hoe zoiets in elkaar zou steken (de taal zal dan waarschijnlijk Java worden gezien java met het rekenwerk sneller kan zijn dan C/C++ er worden namelijk continue optimalisaties uitgevoerd als je het via een HotSpot engine laat lopen).

Option Explicit

Private Sub bereken_Click()
Dim IntGetal As Integer, IntTeller As Integer
Dim isgetalpriem As Boolean
isgetalpriem = True
IntGetal = Val(getal.Text)
For IntTeller = 2 To IntGetal - 1 Step 1
If IntGetal Mod IntTeller = 0 Then
isgetalpriem = False
End If
Next IntTeller
ispriem.Text = isgetalpriem
End Sub

[Anoniem: 23074]

Op woensdag 31 oktober 2001 15:02 schreef ronaldmathies het volgende:
Hier is een klein stukje wat ik heb kunnen vinden over het bepalen of een priem getal een priem getal is.

Ik ga vanavond eens kijken of ik wat kan bedenken om één computer te laten rekenen. (Nog niet distributed) maar het lijkt mij een leuke uitdaging om te kijken of en hoe zoiets in elkaar zou steken (de taal zal dan waarschijnlijk Java worden gezien java met het rekenwerk sneller kan zijn dan C/C++ er worden namelijk continue optimalisaties uitgevoerd als je het via een HotSpot engine laat lopen).

Option Explicit

Private Sub bereken_Click()
Dim IntGetal As Integer, IntTeller As Integer
Dim isgetalpriem As Boolean
isgetalpriem = True
IntGetal = Val(getal.Text)
For IntTeller = 2 To IntGetal - 1 Step 1
If IntGetal Mod IntTeller = 0 Then
isgetalpriem = False
End If
Next IntTeller
ispriem.Text = isgetalpriem
End Sub

Volgens mij is Java egt niet sneller dan C++ (aangezien Java in C++ gemaakt is...)

[rjsomeone]

Op woensdag 31 oktober 2001 14:59 schreef ascii het volgende:

[..]

Yep, 90,79 secs. Maare dit was niet bedoelt als oplossing hoor, slechts om de priemgetallen te bepalen tot de helft van het getal. Enne daar gebruik je geen erp pakket voor hoor.

Eens kijken, voor alle priems tot 600 cijfers geeft dat dus (vooropgesteld dat ik met zeer grote getallen even efficient kan rekenen met die waar ik nu mee reken (not)) eeeuh ongeveer 15 uur stevig stampen.

15 uur? da's weinig, als de 1e 10000000 90 sec duren is de 1e 100000000 900 sec enz. enz. bij elke nul erbij x10, dus
formule (geldend vanaf 7 nullen)
tijd = 9 * 10^(aantalnullen-6), dus een getal van 100 cijfers lang wordt dan:
9*10^96 seconden, ongeveer 6,25*10^23 dagen. beetje te veel denk ik toch

[Anoniem: 38993]

Ik stel voor het in assembler te doen
Zo moeilijk is het niet om ff in 4800+ bits te gaan rekenen, je kan alleen niet de gewone registers ervoor gebruiken.

[Anoniem: 37406]

is er niet een database met priemgetallen ofzo

[rjsomeone]

Op woensdag 31 oktober 2001 15:02 schreef ronaldmathies het volgende:
Hier is een klein stukje wat ik heb kunnen vinden over het bepalen of een priem getal een priem getal is.

Ik ga vanavond eens kijken of ik wat kan bedenken om één computer te laten rekenen. (Nog niet distributed) maar het lijkt mij een leuke uitdaging om te kijken of en hoe zoiets in elkaar zou steken (de taal zal dan waarschijnlijk Java worden gezien java met het rekenwerk sneller kan zijn dan C/C++ er worden namelijk continue optimalisaties uitgevoerd als je het via een HotSpot engine laat lopen).

Option Explicit

Private Sub bereken_Click()
Dim IntGetal As Integer, IntTeller As Integer
Dim isgetalpriem As Boolean
isgetalpriem = True
IntGetal = Val(getal.Text)
For IntTeller = 2 To IntGetal - 1 Step 1
If IntGetal Mod IntTeller = 0 Then
isgetalpriem = False
End If
Next IntTeller
ispriem.Text = isgetalpriem
End Sub

Dit kan toch al veel sneller doorhet volgende toe te veranderen:
For IntTeller = 2 To IntGetal/2 Step 1
If IntGetal Mod IntTeller = 0 Then
isgetalpriem = False
exit for
End If
Next IntTeller

[ronaldmathies]

Ik doe verder niet aan VB of wat het ook moge wezen ik vond dit en plaatste het omdat veel mensen dit wel kunnen. Maar dat stukje code kan je overslaan. Hieronder is een link naar de eerste 6.000.000 priem getallen, dan hoef je deze niet te berekenen, is lekker snel.

http://www.geocities.com/ResearchTriangle/Thinktank/2434/prime/primenumbers.html

Op die manier bespaar je eventuele hoofdbrekens over bepaalde berekeningen.

[Anoniem: 33045]

Op woensdag 31 oktober 2001 12:43 schreef Gerco het volgende:

[..]

[mierenneukmode]
het produkt !
[/mierenneukmode]

Als je het dan doet, doe het dan goed

[goede mierenneukmode]
het produ c t
[/goede mierenneukmode]

[Anoniem: 7477]

Op woensdag 31 oktober 2001 15:05 schreef rjsomeone het volgende:

[..]

15 uur? da's weinig, als de 1e 10000000 90 sec duren is de 1e 100000000 900 sec enz. enz. bij elke nul erbij x10, dus
formule (geldend vanaf 7 nullen)
tijd = 9 * 10^(aantalnullen-6), dus een getal van 100 cijfers lang wordt dan:
9*10^96 seconden, ongeveer 6,25*10^23 dagen. beetje te veel denk ik toch

He fuck, kon het me ook al niet voorstellen en was nog half aan het zoeken naar de fout.

Ik had de (verkeerde) formule tijd = digits^factor en kwam toen tot factor = tijd^(1/digits). Ik kwam uit op een factor = 1,7 (afgerond) En dat gaf dus een aantal uur idpv dagen. Voor me gevoel klopte het ook al niet, maar ik had er verder nog niet naar gekeken (en sta nu voor het )

[reddog33hummer]

een priemgetal heb ik al

HET is 1 !!! LOL

[Anoniem: 31870]

Op woensdag 31 oktober 2001 13:31 schreef HurrI het volgende:

[..]

Alle priemgetallen tot de wortel van dat getal scheelt weer...

maaar niet correct...

alle getallen tot het getal/2 wel

overigens ipv te programeren in een of andere taal. is dit niet beter te programmeren in een rekenprogramma (matlab ofzo)... volgens mij kan je met matlab al alle priem getallen verkrijgen en die getallen in een matrix zetten. het getal delen door die matrix >>> nieuwe matrix waar dus 1 getal een priem getal van is... matrices vergelijken en klaar is kees... (geen idee overigens hoeveel priem getallen het zijn en hoelang het rekenwerk gaat duren)

edit>>>>
hmmm il link hierboven ergens priem getallen te downloaden... en die importeren... iig sneller dan berekenen

[Anoniem: 31870]

Op woensdag 31 oktober 2001 15:25 schreef reddog33hummer het volgende:
een priemgetal heb ik al

HET is 1 !!! LOL

1 is geen priem getal hehe

overigens het getal wat daar staat moet dan ook een priem getal zijn en aangezien dat een produkt is van 2 priemgetallen kan het per definitie nooit een priemgetal zijn.

[Anoniem: 3652]

Ik heb een beetje zitten spele met priemgetallen, zodat ik een manier kon vinden die werkt voor dit probleem. Dit klinkt waarschijnlijk een beetje weird, en ik weet ook niet of het klopt bij hogere getallen.

Stel, je neemt de getallen 17 en 23.
17x23 = 391.
de wortel van 391 is 19,77 (ongeveer)
rond het naar boven af.

20x20 = 400
17-20 = -3
23-20 = 3
-3x3 = 9
400-9 = 391

Dit werkt met de getallen 17 en 23, 19 en 23, 13 en 23 (23 was het hoogste priemgetal wat ik snel even uit mijn hoofd kon uitrekenen. )

Dus als het goed is moet je dat getal op de volgende manier kunnen kraken.
1. neem de wortel van code.
2. rond deze naar boven af.
3. doe deze wortel in het kwadraat.
4. haal het kwadraat van de code af.
5. neem van deze uitkomst weer de wortel, dit moet als het goed is een geheel getal zijn.
6. haal van het getal wat je bij stap 2 hebt gevonden 1 keer het getal van stap 5 af, en tel er 1 keer het getal van stap 5 bij op.

Als het goed is heb je nu de getallen die je zoekt.

[Anoniem: 31870]

Op woensdag 31 oktober 2001 15:16 schreef MaxNatic het volgende:

[..]

Als je het dan doet, doe het dan goed

[goede mierenneukmode]
het produ c t
[/goede mierenneukmode]

haha nee dus... produKt is goed aangezien dit niet van het werkwoord produceren afkomt... maar een wiskundige term is

[Anoniem: 38993]

Op woensdag 31 oktober 2001 15:36 schreef GHOst. het volgende:

<snip>
Dus als het goed is moet je dat getal op de volgende manier kunnen kraken.
1. neem de wortel van code.
</snip>

Wel's low-level een wortel proberen uit te rekenen? En probeer dat eens op een getal van 600+ digits (4800+ bits) te doen, not to mention dat die wortel een waarschijnlijk een prachtig komma-getal wordt

[Anoniem: 7477]

Ik was nog even verder aan het denken (maar misschien weer verkeerd, net zoals al eerder). Maar als het al lukt om binnen een redelijke termijn voor alle getallen onder de 10^600 de priemgetallen te gaan berekenen, dan moet het resultaat nog worden opgeslagen. De kleinste manier om dat te doen is 1 bitje gebruiken voor elk getal. Alleen dat is minimaal 10^600 bitjes. Eeeuh, grof afgerond 10^599 byte (ik weet het een byte is 8 bitten, niet 10) Dan nog even verder zeer grof afronden, 10^596 KB (ja voor 1 kilobyte heb ik even 1000 genomen en niet 1024) eeeeeuh 10^587 TB. Zut, behalve dat deze methode rekend tot het eind der tijden hebben we ook nog bijna onbeperkte opslag ruimte nodig. Oke leuk probleem, ik ga iets anders doen.

(als ik nu weer een domme fout heb gemaakt zal ik nooit meer reageren)

[rjsomeone]

1. neem de wortel van code.
2. rond deze naar boven af.
3. doe deze wortel in het kwadraat.
4. haal het kwadraat van de code af.
5. neem van deze uitkomst weer de wortel, dit moet als het goed is een geheel getal zijn.
6. haal van het getal wat je bij stap 2 hebt gevonden 1 keer het getal van stap 5 af, en tel er 1 keer het getal van stap 5 bij op.

Als het goed is heb je nu de getallen die je zoekt.

Jammer.. ik dacht ff dat je 'effetjes' het hele priemgetallen probleem had opgelost.
Maar als je bijv. de priemgetallen 677 en 761 neemt (product is 515197), klopt 't helaas niet meer, afgerond naar boven geeft dit 718, 718^2 geeft 515524, 515197-515524=-327, daar de wortel van kan eigenlijk niet, maar is dus 18,nogwat(niet geheel getal), en 718+18(en nogwat) komt niet in de buurt van 761 helaas.. 718-18 ook niet bij 677..

[drm]

Op woensdag 31 oktober 2001 15:36 schreef betweter het volgende:

[..]

haha nee dus... produKt is goed aangezien dit niet van het werkwoord produceren afkomt... maar een wiskundige term is

je doet je nick wel eer aan, zeg

Van Dale:

bij zoeken op product:

pro·Žduct (het ~)

_{1 voortbrengsel van de natuur, van arbeid of nijverheid, van kunst, van een chemisch proces => resultaat
2 [wisk.] uitkomst van een vermenigvuldiging
3 de totale waarde van de productie
4 [jur.] voorgelegd stuk}

bij zoeken op produkt:

ho, niks

//offtopic


Kunnen we niet deze computer even lenen?

[Anoniem: 3652]

Op woensdag 31 oktober 2001 15:43 schreef trie het volgende:

[..]

Wel's low-level een wortel proberen uit te rekenen? En probeer dat eens op een getal van 600+ digits (4800+ bits) te doen, not to mention dat die wortel een waarschijnlijk een prachtig komma-getal wordt

Ik weet niet eens hoe ik een wortel uit moet rekenen zonder reken machine. Maar om even op jouw post in te gaan:
1. hoezo low level? als dit werkt kun je het in de langzaamste taal maken die je kent, en het werkt nog steeds sneller dan de andere manieren die we hier hebben gezien.
2. het getal is een 2048 bits code volgens RSAlabs, maar we kunnen ook aan die 512 bits code beginnen. Zou in principe niet veel langzamer moeten werken.
3. er komt zeker een decimaal getal uit, maar als je naar boven af rond heb je daar toch geen last meer van.

[edit]

Jammer.. ik dacht ff dat je 'effetjes' het hele priemgetallen probleem had opgelost.
Maar als je bijv. de priemgetallen 677 en 761 neemt (product is 515197), klopt 't helaas niet meer, afgerond naar boven geeft dit 718, 718^2 geeft 515524, 515197-515524=-327, daar de wortel van kan eigenlijk niet, maar is dus 18,nogwat(niet geheel getal), en 718+18(en nogwat) komt niet in de buurt van 761 helaas.. 718-18 ook niet bij 677..

hmm. je hebt gelijk. MAARRRRRRR als je 719 neemt ipv 718, dus het getal wat precies tussen die priemgetallen in zit, dan klopt het weer wel.
Het is dus zeker de moeite waard om even naar die methode te kijken.

[Anoniem: 7477]

Op woensdag 31 oktober 2001 15:36 schreef GHOst. het volgende:
Dus als het goed is moet je dat getal op de volgende manier kunnen kraken.
1. neem de wortel van code.
2. rond deze naar boven af.
3. doe deze wortel in het kwadraat.
4. haal het kwadraat van de code af.
5. neem van deze uitkomst weer de wortel, dit moet als het goed is een geheel getal zijn.
6. haal van het getal wat je bij stap 2 hebt gevonden 1 keer het getal van stap 5 af, en tel er 1 keer het getal van stap 5 bij op.

Als het goed is heb je nu de getallen die je zoekt.

Hmm
priem 11 maal priem 73 is 803

oftewel
1. wortel van 803 is 28,34...
2. ongeveer 29
3. 841
4. 803 - 841 = -38
5. wortel van 38 is 6,1644 etc eeuh geen geheel getal helaas

Darn, maar zou ook wel te simpel zijn.

[Anoniem: 38998]

Een berekening met de zeef van Erasthones is onzin (alle priemgetallen die je vind verzamelen en gebruiken om te bepalen of het volgende getal priemgetal is).

Eventjes een paar getallen. Als je een getal hebt van 174 cijfers dan is de wortel 87 cijfers lang. Als je er vanuit gaat dat er gemiddeld minimaal 1 priemgetal per tiental zit dan wil dit zeggen dat er 10^86 priemgetallen zijn te berekenen voordat je bij 10^87 komt. Deze priemgetallen zijn gemiddeld 10^43 = 43 cijfers = 121 bits = 15 bytes groot. 10^86 * 15 bytes betekend dat je 1.5 * 10^87 bytes nodig hebt om de getallen op te slaan. Als de hele wereld mee zou werken en allemaal een schijf van 100 Gig zouden hebben (6 * 10^9 * 100 * 10^9 = 6 * 10^20) zouden we 6 * 10^20 bytes hebben. We zouden dus nog 10^60 werelden nodig hebben om de getallen op te slaan.

Dit is alleen de opslagruimte die je nodig hebt. Indien je 90 sec over de eerste 10.000.000 getallen doet, dan wil dit niet eens zeggen dat je 900 seconden over een tienvoud doet. Je moet namelijk niet alleen 10 keer zoveel getallen bekijken maar ook door 10 keer zoveel getallen delen, dwz 100 keer zoveel tijd.

Je zult dus een andere (niet brute force) methode moeten vinden. Het heeft wel als voordeel dat waarschijnlijk meteen een baan kunt krijgen bij de NSA of een
willekeurige andere geheime dienst.

[Anoniem: 23074]

Op woensdag 31 oktober 2001 15:56 schreef tyler het volgende:
Een berekening met de zeef van Erasthones is onzin (alle priemgetallen die je vind verzamelen en gebruiken om te bepalen of het volgende getal priemgetal is).

Eventjes een paar getallen. Als je een getal hebt van 174 cijfers dan is de wortel 87 cijfers lang. Als je er vanuit gaat dat er gemiddeld minimaal 1 priemgetal per tiental zit dan wil dit zeggen dat er 10^86 priemgetallen zijn te berekenen voordat je bij 10^87 komt. Deze priemgetallen zijn gemiddeld 10^43 = 43 cijfers = 121 bits = 15 bytes groot. 10^86 * 15 bytes betekend dat je 1.5 * 10^87 bytes nodig hebt om de getallen op te slaan. Als de hele wereld mee zou werken en allemaal een schijf van 100 Gig zouden hebben (6 * 10^9 * 100 * 10^9 = 6 * 10^20) zouden we 6 * 10^20 bytes hebben. We zouden dus nog 10^60 werelden nodig hebben om de getallen op te slaan.

Dit is alleen de opslagruimte die je nodig hebt. Indien je 90 sec over de eerste 10.000.000 getallen doet, dan wil dit niet eens zeggen dat je 900 seconden over een tienvoud doet. Je moet namelijk niet alleen 10 keer zoveel getallen bekijken maar ook door 10 keer zoveel getallen delen, dwz 100 keer zoveel tijd.

Je zult dus een andere (niet brute force) methode moeten vinden. Het heeft wel als voordeel dat waarschijnlijk meteen een baan kunt krijgen bij de NSA of een
willekeurige andere geheime dienst.

Maar opzich lijkt me het wel leuk, om dit als "Tweakers.net" voor mekaar te krijgen, ik zie het al voor me: Hier is Piet Paulusma, bij de Tweakers, die de RSA code gehacked hebben

[Anoniem: 7477]

Op woensdag 31 oktober 2001 15:56 schreef tyler het volgende:
Je zult dus een andere (niet brute force) methode moeten vinden. Het heeft wel als voordeel dat waarschijnlijk meteen een baan kunt krijgen bij de NSA of een
willekeurige andere geheime dienst.

idd, maar dat maakt het niet minder leuk om over dit soort dingen na te denken. Gewoon om je grijze massa even te prikkelen, een beetje lol mag toch ook?

[Anoniem: 3652]

k heb mijn methode nog eens bekeken, en er klopt inderdaad niet zo heel veel van. Ik heb nu wel iets bedacht waarmee het wel brute force gaat, maar waarvoor je nog steeds geen priemgetallen nodig hebt. Waar het eigenlijk om draait is hoe ver die priemgetallen uit elkaar liggen.
Voorbeeldje aan de hand van de getallen die eerder in dit draadje staan.
11x73 = 803
het gemiddelde van 11 en 73 is 42.
42^2 = 1764
1764-803 = 961
sqrt(961) = 31
42 - 31 = 11
42 + 31 = 73.

Aangezien we de priemgetallen niet weten, en dus ook niet het gemiddelde weten, moeten we dit dus zoeken. Maar als we eenmaal weten hoe ver die getallen uit elkaar liggen of wat het gemiddelde van die getallen is, dan weten we ook welke getallen we zoeken.

[Anoniem: 38998]

Op woensdag 31 oktober 2001 16:08 schreef ascii het volgende:

[..]

idd, maar dat maakt het niet minder leuk om over dit soort dingen na te denken. Gewoon om je grijze massa even te prikkelen, een beetje lol mag toch ook?

Uhhh ik vind het ook leuk om erover na te denken. Gaf alleen aan welke methode geen zin heeft .

[Anoniem: 23074]

Op woensdag 31 oktober 2001 16:24 schreef GHOst. het volgende:
k heb mijn methode nog eens bekeken, en er klopt inderdaad niet zo heel veel van. Ik heb nu wel iets bedacht waarmee het wel brute force gaat, maar waarvoor je nog steeds geen priemgetallen nodig hebt. Waar het eigenlijk om draait is hoe ver die priemgetallen uit elkaar liggen.
Voorbeeldje aan de hand van de getallen die eerder in dit draadje staan.
11x73 = 803
het gemiddelde van 11 en 73 is 42.
42^2 = 1764
1764-803 = 961
sqrt(961) = 31
42 - 31 = 11
42 + 31 = 73.

Aangezien we de priemgetallen niet weten, en dus ook niet het gemiddelde weten, moeten we dit dus zoeken. Maar als we eenmaal weten hoe ver die getallen uit elkaar liggen of wat het gemiddelde van die getallen is, dan weten we ook welke getallen we zoeken.

jep, maar dat is random, dus...

[Munters]

Op woensdag 31 oktober 2001 15:43 schreef trie het volgende:

[..]

Wel's low-level een wortel proberen uit te rekenen? En probeer dat eens op een getal van 600+ digits (4800+ bits) te doen, not to mention dat die wortel een waarschijnlijk een prachtig komma-getal wordt

Er zijn algoritmes om met de hand wortels uit te rekenen hoor. Maar niet meer zo bekend sinds de opkomst van de zakjappanner.

Overigens is het bepalen van die wortel niet zo moeilijk hoor. Daar hebben we tenslotte bc/dc voor en die geeft:
15873219105039120417448250866106300
75793584634448097157957266277535799
70080749948404278643259568101132671
40205619002146475341948047281684064
61685752226289346714057392134774395
33870489791038973166834068736234020
36166482026698772691945335682413800
73819857964936212330351128493730474
84148339095287142097834807844
met rest natuurlijk, anders was het wel heel gemakkelijk.

Indien we deze wortel even w noemen is het aantal priemgetallen tot aan w ongeveer gelijk aan w/log(w).
Praktisch niet bruikbaar allemaal. Logisch ook, daar zijn immers alle huidige cryptografische systemen op gebaseerd.

rc-64 is een typisch voorbeeld van een distributed aanpak voor dit soort problemen. Loopt nu al >1300 dagen gok ik zo.

Gaan we natuurlijk niet na proberen te doen. Overigens is een deel-algoritme voor grote getallen niet echt moeilijk. Je bouwt gewoon na wat je vroeger op school geleerd hebt: staartdeling. (Of leer je dat niet meer tegenwoordig?)

'k Heb het ooit nog eens geimplementeerd op m'n C64 in assembler om perfecte getallen (getallen waarbij de delers opgetelt het oorspronkelijke getal teruggeven, bijvoorbeeld 6 = 1 + 2 + 3 of 28 = 1 + 2 + 4 + 7 + 14) te berekenen. Heb ik de machine nog eens drie maanden aan laten rekenen...en toen had ie de eerste 6 of 7 getallen gevonden.
Was wel geinig, want door het videogeheugen daarvoor te gebruiken kon je automatisch volgen waar de machine mee bezig was.

[Anoniem: 23074]

Waarom zouden we het niet zo doen? (ff lekker bruut)

je hebt bijvoorbeeld een code (voor het gemak ff 123456)
De client logt in op het CGI'tje, die kijkt in zijn database, wat die gene moet pakken, en dat stuurt ie door...

De ene heeft dus bijvoorbeeld: 1 - 1000 X 1 - 1000
de volgende: 1001-2000 X 1-1000

Wat je dan erbij kan doen (om het sneller te maken) is bijvoorbeeld:

als je een getal met 6 nullen hebt (bijvoorbeeld 1000000) en je moet 5001 - 6000 X 6001 - 7000, dat kan natuurlijk nooit, omdat 5001 X 6001 al groter is dan de code...

[.oisyn]

Ik zie dat jullie met mijn idee aan de haal zijn geweest...

Maar gelukkig heb ik het gepatenteerd, dus als jullie dit nou effe maken, dan span ik aan het eind wel een rechtzaak aan.

* .oisyn feels like Rambus, Inc.

[Jelmer]

Op woensdag 31 oktober 2001 16:29 schreef Munters het volgende:
w/log(w)

uh, log als in natuurlijke log dan wel munters. Toch HurrI? (Hebben allebei tentamen widi (discrete wiskunde) gehad vandaag waar veel over priemetjes gsproken wordt)

--
Nog ff een uitbreiding van de 'tentamenstof':
Hier meer info:
[knip]layout fucked up[/knip]

www.icim.fnt.hvu.nl/vak/3widi1/
(dit bovenstaan de stuk kwam uit de subdir Week14, bestand Coll14.doc (word))

[.oisyn]

haha zit jij ook op de hvu

[Jelmer]

offtopic:
volgens mij half /14...

[jvdmeer]

84% van de mogelijke producten zijn al standaard onmogelijk, want het voorbeeld getal eindigt op een 7, en een product eindigt alleen op een 7 als de factoren eindigen op (1 en 7) of op (3 en 9).

Alle andere combinatie's van eindcijfers geven een verkeerd eindcijfer!

Scheelt heel erg veel werk!

[edit]Percentage aangepast (4 combinaties vallen af van de 25 (alleen oneven getallen))[/edit

[Anoniem: 3652]

even doorgaan op mijn methode:
Sqrt((X^2)+code)= een geheel getal (GT)
GT - X = Priem 1
GT + X = Priem 2

X < (Sqrt(code))/2

Om X te zoeken kun je pakketjes maken van bijvoorbeeld 1.000.000 sleutels. En dan maar distributen.
Voor de database heb je dan veel minder ruimte nodig, en wat netwerk verkeer betreft heb je ook heel erg weinig nodig...

[Munters]

Op woensdag 31 oktober 2001 15:08 schreef fladder het volgende:
is er niet een database met priemgetallen ofzo

Alle priemen < 2*10^9 zijn te vinden op:
http://www.rsok.com/~jrm/printprimes.html

Toevoeging:

Het berekenen van priemen met de zeef blijkt zo efficient te zijn dat ze sneller berekent kunnen worden dan uit een lokale disk file (dus laat staan een db over het net)gelezen te kunnen worden.

Tot aan 10^9 zijn er precies 50847534 priemen. Dan heb je het al gauw over een 400MB bestand.
Snelste progje dat ik vond berekent deze priemen in 5,7 seconden op een PII/500 (die ook nog wat andere dingen te doen doen had)! (Dit is zonder omzetten naar decimaal en zonder weergave).

[Jelmer]

kijk daar heb je wat aan
Nu kan je dus die 2e formule gebruiken uit paragraaf 4.3 die in het document staat waar ik in mijn vorige post naar verwees. (de z.g. Miller-Rabin-test)

[rjsomeone]

Op woensdag 31 oktober 2001 16:31 schreef KixAss456 het volgende:
Waarom zouden we het niet zo doen? (ff lekker bruut)

je hebt bijvoorbeeld een code (voor het gemak ff 123456)
De client logt in op het CGI'tje, die kijkt in zijn database, wat die gene moet pakken, en dat stuurt ie door...

De ene heeft dus bijvoorbeeld: 1 - 1000 X 1 - 1000
de volgende: 1001-2000 X 1-1000

Wat je dan erbij kan doen (om het sneller te maken) is bijvoorbeeld:

als je een getal met 6 nullen hebt (bijvoorbeeld 1000000) en je moet 5001 - 6000 X 6001 - 7000, dat kan natuurlijk nooit, omdat 5001 X 6001 al groter is dan de code...

Is dat sneller dan gewoon paketjes halen van 100000 nummertjes (van 2 tot de helft - 1 van het getal), en dan gewoon kijken of er na deling een rest is (Mod in VB)?

[rjsomeone]

Ik weet niet of dit nuttig is, maar toch:

10 x 10 = 100 <-- kleinste gemiddelde: 10
1 x 100 = 100 <-- grootste gemiddelde: 50,5

8 x 8 = 64 <-- kleinste gemiddelde: 8
1 x 64 = 64 <-- grootste gemiddelde: 32,5

Dus de gemiddelden van de 2 priemen ligt bij 't laatste voorbeeld tussen 8 en 32,5, anders gezegd:

Het gemiddelde van de 2 priemen van het getal RSA ligt tussen: Sqr(RSA getal)
en Sqr(RSA)*.5*Sqr(RSA)+0.5.
Volgens mij klopt dit voor alle getallen die bestaan uit 2 priemgetallen.

[The - DDD]

Die eenvoudigste van al die getallen (174 decimalen) is slechts 72 bytes lang (uche)...

Hoe bepaald?

Zo (sorry voor het verknooien van de layout):

code:

import java.math.BigInteger;

public class test {

    public static void main (String args[]) {
      BigInteger bigInt = new BigInteger("188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059");
      System.out.println("The number of bits: " + bigInt.bitLength());
    }

}

[The - DDD]

Geeft dus aan dat er wat betreft java doodeenvoudig met zo'n getal gewerkt kan worden.

Dus euh, leef je uit...

Hmmm, dat geval van 617 decimalen is dus: 2048 bits oftewel: 256 byte...

Sick, een getal van een kwart meg..
Oh ja, java kan dat dus ook aan.

Verder vraag ik me wel iets af. Hoe de fuck kan je dit ooit gedistribueerd gaan uitrekenen? Want stel dat je een java progje en server app maakt voor het number crunchen, hoe pak je zoiets aan. Ik ben niet van plan het te gaan doen, maar het principe erachter vraag ik me wel een beetje af.

[Infinitive]

Gaan jullie maar lekker proberen die code te kraken

Waarom denk je dat die code op die website staat? Hiermee willen ze vast aantonen dat binnen redelijke tijd dat haast niet te doen is...

[.oisyn]

Op woensdag 31 oktober 2001 19:56 schreef The - DDD het volgende:
Geeft dus aan dat er wat betreft java doodeenvoudig met zo'n getal gewerkt kan worden.

Dus euh, leef je uit...

Hmmm, dat geval van 617 decimalen is dus: 2048 bits oftewel: 256 byte...

Sick, een getal van een kwart meg..
Oh ja, java kan dat dus ook aan.

uhm ja, maar dat stond er al bij, dat het zoveel bits was

En maak daar maar een kwart kilobyte van

[Anoniem: 23074]

Dat zou heel mooi zijn, want aangezien java platform onafhankelijk is, kunnen de linux users hiero dus ook mee doen

[The - DDD]

Op woensdag 31 oktober 2001 20:01 schreef OiSyN het volgende:

[..]

uhm ja, maar dat stond er al bij, dat het zoveel bits was

En maak daar maar een kwart kilobyte van

Zie ik nu ook, enne de uitkomst van dat java progje komt niet overeen met wat er op die site staat.... Die lui hebben het niet goed geteld!!

Leuke van dit soort geintjes is dat het makkelijker is om zo'n rotgetal te bepalen dan uit te rekenen wat de oorspronkelijke priemgetallen waren.

[The - DDD]

Op woensdag 31 oktober 2001 20:01 schreef OiSyN het volgende:

[..]

uhm ja, maar dat stond er al bij, dat het zoveel bits was

En maak daar maar een kwart kilobyte van

[vrouwelijk geslachtsdeel], je hebt gelijk...

[rjsomeone]

Welk algoritme gaan we nu gebruiken? Kunnen we iets van een poll houden ?

[The - DDD]

Op woensdag 31 oktober 2001 20:06 schreef rjsomeone het volgende:
Welk algoritme gaan we nu gebruiken? Kunnen we iets van een poll houden:) ?

Denk dat het schatten van de rekentijd ook wel nuttig zal zijn (om vervolgens de hoop op te geven ).