Skočiť na obsah

Matematika


robopol

Odporúčané príspevky

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. 

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

pred 9 minútami, robopol napísal:

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

Screenshot - 11_ 9.jpg

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. 

Odkaz na príspevok
Zdieľať na iných stránkach

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

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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/

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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š?

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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:

 

Screenshot - 21_ 9.jpg

Odkaz na príspevok
Zdieľať na iných stránkach

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...

  • Pridať bod 1
Odkaz na príspevok
Zdieľať na iných stránkach

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

Odkaz na príspevok
Zdieľať na iných stránkach

Vytvorte si účet alebo sa prihláste, aby ste mohli písať príspevky

Ak chcete odoslať príspevok, musíte byť členom

Vytvoriť konto

Zaregistrujte si nový účet v našej komunite. Je to ľahké!

Zaregistrovať si nové konto

Prihlásiť sa

Máte už konto? Prihláste sa tu.

Prihlásiť sa teraz
×
×
  • Vytvoriť nové...

Dôležitá informácia

Táto stránka používa súbory cookies, pre zlepšenie používania stránok tohto webu. Pre viac informácií kliknite sem. Ďalšie informácie nájdete na stránke Zásady ochrany osobných údajov