Matematika

mne to stale vyhadzuje toto, na čokolvek rovnake okno hlasenia

pred 16 minútami, robopol napísal:

ale urob tam tie dva body, pretože to si ho značne spomalil, to je jasne, že v takej podobe ako je horsi.

Ja ťa nekritizujem, preto som chcel, aby si algoritmus napísal ty. Podľa mňa tie úpravy môžeš spraviť v Excely, keď nebudeš plniť  všetky bunky m,n, môžeš zadať velké číslo. 

jasne možem to urbit, jasne aj v c++, aj v comkolvek. Myslel som, že teba zaujima ta rýchlost, že ta to bavi to naprogramovat. Mne sa len zda, že to je porovnatelne (ak urobis upravy). Pisal som zaleži na nahode ake číslo si vyberieš, niektore urobi algoritmus lepšie ine horšie. To čo som ti hovoril, ak by si chcel je vytvorit to pre Mersenove čísla a tam to určite bude konkurent čomukolvek, k tomu sme sa nedostali, lebo sme riesili zaklady. tam je nutne zvladat pracovat s milionom číslic.

pred 9 minútami, robopol napísal:

mne to stale vyhadzuje toto, na čokolvek rovnake okno hlasenia

Ja som zmätkár, ale stiahol som si súbor z odkazu a funguje mi. Neviem či ti neberie ten starý z pamate. Skúsim ho premenovať . Premenoval som ho na Project_001.zip. 

tak mi ale musis dat odkaz na ten project001.zip, mam len na ten druhy chybny.

Ok, uz ho mam ten spravny odkaz.

program funguje. Na tých vačších prvočíslach to už nezvláda prejst taku dlhú periódu. (neni sa čo čudovať),

Druhy algoritmus ide do sqrt(p), čo je značný rozdiel oproti (p-1)/2

tak ma napadlo taká vec, že čo keby sme urobili taku vec, že ak nenajde kratšiu periodu ako sqrt(p-1) tak to bude prvočíslo, alebo pseudoprvočíslo, zložené čísla zrejme nemôžu mať dlhšie periody.

Budem sa tomu neskôr venovať, ale teraz musím niečo v robote dokončiť... Ak máš nápad, skús zmeniť iba tú časť algoritmu, ktorú som uviedol. (Môžeš tam vsunúť iba text s popisom, ja sa to pokúsim prepísať.) 

Ja som to testoval aj na Mathcade a tam to ide brutálne rýchlo. Neviem, aké algoritmy tam používajú, ale PC je to isté a čas je úplne mimo. Číslo p (cca 2800 cifier)

p := 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001283

vyhodnotí ako prvočíslo  na kliknutie. Čas meria je po 0,01s a pri tejto operácii to bolo menej, lebo hodiny sa ani nepohli.. Takéto prvočísla predsa nemôžu mať hotové v databáze

To budu pravdepodobnostne algoritmy, teda nevies na isto či to je prvočíslo. Však ten Rabinov test je tiež volne dostupny a možes ho v prípade zaujmu implementovať, pre porovnanie. Eratonovo sito tiež. Tu su take dva klasicke. Rabinov test produkuje aj pseudoprvočísla.

Ja myslím, že nemá velký význam sa venovať nejakej špecialnej optimalizácii algoritmu, to nemá žiadne využitie, bežny uživateľ pc potrebuje vediet male prvočísla. Význam môžu mat tie Mersenove čísla, tam sú periody krátke a vieme ich dopredu zrátat. To sa da využiť pre optimalizaciu.

ZMENY ALGORITMU

1.algoritmus obmedzis na hladanie pre i=sqrt(p), ak dovtedy nenájde periodu teda m=p, alebo m=4, ide o prvočíslo (pre tie velké prvočísla). Toto by teda mohlo platit ako som pozeral, pre male čísla môžu byť výnimky so sqrt(p). PS: neplati to univerzálne, len s nejakou vačšou pravdepodobnostou.

2.zadefinuj N=(p-1)/2,

3. daj podmienku, že keď najde PRVE m=p, alebo m=4, potom ak N/i=integer, potom je to prvočíslo, ak nie potom je to zlozene.

4.v cykle pre m, n urob zmenu takuto:

ak je m : párne, potom   urob výpočet m, Ak je nové m párne, neni treba rátat n, pokial je m :nepárne vyrátaš n=p-m

ak je n párne, potom urob výpočt n, Ak je nové n párne, není treba rátat m, pokial je n: nepárne vyrátaš m=p-n

5. ak je číslo rozložitelne do tvaru p=2^k+-1, k=1,2..... potom periody su k a 2k. Tieto periody sú krátke a majú ich prvočísla.

pred 51 minútami, robopol napísal:

 bežny uživateľ pc potrebuje vediet male prvočísla.

Ja využívam mikrokontroléry od Texas Instruments a tie majú HW implementovanú RSA. Nikdy som to síce nepotreboval, ale jednoúčelový sekvenčný HW nemá v rýchlosti konkurenciu.

Robil som rýchlu  Fourierovu transformáciu a najprv som program dolaďoval v 8 jadrovom  PC s využitím vlákien. Bolo to žalostne pomalé, lebo to malo merať v reálnom čase. Mikrokontrolér s HW násobičkou to zvládol 1000x rýchlejšie. Samozrejme "neotravoval" ho pri tom operačný systém. Čo sa dá dnes spraviť na bežných mikrokontroléroch je úžasné. Aké možnosti sú dnes v armádnom výskume, to ani netuším.  

A ešte ma napadlo, pri GPS sa rieši sústava minimálne 4 rovníc, kde neznáme sú x^2, y^2, z^2, t^2. Ja som sa o to pokúšal, ale nepodarilo sa mi to. A čo tak sústava pre 12 satelitov. Ten malý čip dokáže vyriešiť takúto sústavu minimálne 10x za sekundu.

pred 41 minútami, robopol napísal:

To budu pravdepodobnostne algoritmy, teda nevies na isto či to je prvočíslo.

Ak by pri RSA neboli použité prvočísla, ale iba z určitou pravdepodobnosťou, tak by výsledok použitej dvojice vybraných čísel nebol jednoznačný. To by bol asi riadny bordel.

pred 58 minútami, Tono napísal:

Ak by pri RSA neboli použité prvočísla, ale iba z určitou pravdepodobnosťou, tak by výsledok použitej dvojice vybraných čísel nebol jednoznačný. To by bol asi riadny bordel.

ja ale hovorim o rychlom prevereni čísla, tam sa pouzivaju pravdepdobnostne algoritmy. Pri šifrovani to ale musíš vediet na isto.

nechápem jednej veci Rabinov test je využitie uprava Fermatovej vety, ako môže ist rýchlejšie pre vlké prvočísla, ved tam su tak brutalne mocniny, že nechapem ako je to možné...

https://www.geeksforgeeks.org/primality-test-set-3-miller-rabin/

Tono, už som zistli prečo, je ten Rabin test dobry, binarne umocnovanie ide rýchlo a ešte sa to dá vylepšiť cez Fouriera, my sme neumocnovali nic a išli sme s algorimom do (p-1)/2. Nebolo treba.

Tak to troška zo zábavy programujem, pri velkých mocninach treba urobit konverziu do hex a potom spat. Metoda je zrovnatelna s Miller Rabin test (teda menej ako sqrt(n)). Zaujimave je to, že mi ten Rabin test vyhadzuje chybny výsledok (niekedy) pri a^b mod n. Co nechapem neviem v čom je problem. Mod by mal pc vyratat spravne, taku chybu som nikdy nemal (premenne su v poriadku).

Inak pre tvoju informáciu Tono. Algoritmus (m,n) je primarne určený na redukciu vysokých mocnín. Od určitej velkosti musí byť znižovanie mocniny efektivnejšie ako umocnovanie s obrovským základom. Kedže sú čísla, ktoré dovoluje velkost premenných nízke, tak je rýchlejšie umocnovanie, ako znižovanie cez (m,n). Algoritmus, však odhaluje krátke periody čísiel, nejde do polovice n/2. Zastaví sa po rozumnej velkosti preskúmani a prejde do výpočtu mocnín Fermatovej vety (s využítim) vlastnosti ktorú využíva Miler- Rabin.

Tak a apodarilo sa to dotiahnut do very fast metody. Konečne som vyriešil problem, čo sa mi zdalo nemožne vyriešiť, vďaka nemu sa daju mocniny redukovat daleko rýchlejšie, som debil, že ma to nenapadlo, ked som sa tomu venoval. Miler - Rabin test sa schová do zadku. Progam dorobim a odladim pre rozumne velke čísla na predstavu, pojde to okamžite bez čakania.

pred 9 hodinami, robopol napísal:

Tak to troška zo zábavy programujem,

Je dobré, že si to môžeš otestovať v reálnom čase. Je celkom bežné, že pri programovaní zistíš, kde je problém v čase daného algoritmu.  V jakom jazyku to programuješ?

ja pouzivam visual basic, ten poznam najlepšie. Ano, coskoro to bude, ak sa nemylim, tak to je rýchclejšie ako Rabin - Miler (o dost), to sa dá ale zistit az pri číslach nad 30 čislic, predpokladam, tak 100-200, to budem musiet vyriesit do nebude stacit to transformat do hex a spat do dec.

oprava

Tono

program a algoritmus mam uz urobeny. Mal by byt rychlejsi ako Rabin - Miller (o niečo, z hladiska metody vidim menšiu vypočtovu narocnost).Problem je stale to iste, bez uprav to robi čísla do zhruba 1000. pretože mocnina pretečie cez velkost formatu.

zatial teda som sa dostal k tomu, že cislo prevediem na Hex. Mam aj transformaciu na integer. Lenže tu treba urobit ešte mocninu s hex cislami a modus s hex. číslami. Možno by to bolo lepšie previest na binarnu formu čísla.

nemam zatial algoritmus ako urobit tie mocniny a modus. Ak vieš poradit, tak napís.

Kto neveri nech klikne na rovnicu,

zovšeobecnil som periody pre prvočísla, výpočet Mersenovho čísla zvladne bezny program, alebo aplikacia Wolfram

pre základ a=2 Fermatovej vety

https://www.wolframalpha.com/input/?i=2^82589934-2+mod+(2^82589933-1)

PS: s touto rovnicou moze vyhladat kazdy ešte vačšie prvočíslo.

tato rovnica palti pre lubovolne Mersenove prvočíslo:

@robopol vypočítaj pravdepodobnost vyskytu zivota vo vesmíre 

na to pre nás myslím celkom stačí Drakeova rovnica... iné tam ťažko primyslieť :)

Tak, ale musite uznat, že to je elegatne vyhldanie nie?

To prve uvedene Mersennovo číslo ma 2-3 miliony číslic. Ta rovnica plati pre kazde Mersenovo prvočíslo, napr.

2^34=2147483647  (Nasiel Euler)

a dosadenim do tej rovnice máme vysledok okamzite

https://www.wolframalpha.com/input/?i=2^32+-2+mod+(2^31-1)

PS: vyratat pravdepodobnosti je tazke, pretože u inteligetneho života nemame žiadne dobre voditko. Drakeova rovnica to nevie vyriešit, tam su bulharske konštanty...

veď, o tom píšem :)... milujem Drakeovu rovnicu snáď odjakživa, ale ešte ináč vyrátať pravdepodobnosť života je vlastne nemožné.

to nie je matematika, vlastne ani pravdepodobnosť, to je ruleta s neznámym množstvom možných núl

No ved ano, kazdy píše o niečom inom :) Tato tu uvdená rovnica na rozdiel od Drakeovej funguje skvele :)

článok o periódach prvočísiel:

https://robopol.sk/blog/very-fast-algoritmus-na-prvocisla

urobil som par korekcii v članku a obrazkoch, boli tam drobne chyby.