Matematika

Tono to je tak jednoduchce, že posielat niečo je úplne zbytočne, videl si tie excelovske tabulky (golden part- diel)? to ti nie je jasne z toho, že nechaš dobehnut algoritmus (primitivne vztahy) do m,n (p,0), pričom prejdeš n=(p-1)/2 a výsledok pre prvočísla musí byt (p,0) alebo (4, p-4). Hotovo. Pre zmeišane číslo to neplati a objavi sa m,n (p,0) skor. Toto je ten algoritmus, čo ti mam prepisat? :)

Mozeš ušetrit výkon aj na výpočtr m(i), n(i) tak, že pokial je výsledok párne číslo, tak nemusís vyčíslit tu druhu premennu. Lebo nasledujuca hodnota sa odvija len od párneho čísla z dvojice m(i), n(i).

1 bod- deklaruješ premenne

2 bod-zadefinujes algoritmus m(i), n(i) v cykle, vztahy su na obr.

3 bod stopnes prog na podmienky (p,0) alebo (4,p-4)

4 bod porvnas (i) v cykle, ak je (i) na stope zhodné s (p-1)/2, potom je to prvočíslo, ak nie potom je to zmeišane.

Dňa 10. 9. 2020 at 16:04, robopol napísal:

Tono,

Ak chceš urbim to vo visual studiu (aj ked sa mi moc nechce :) )

Netráp sa s tým. Ja som len chcel, aby si si spravil program ty, lebo ak ho spravím ja, tak môžeš namietať, že nie je efektívny. V c++ to bude obmedzené na long long, čo je 2^64, to by malo pre test stačiť. Aké veľké má byť N v cykle?

Nerozumiem otazke? for i:1 to N,

to znamena cyklus ide dovtedy, kým nedosiahne bod 3, čo je podmienka na ukoncenie cyklu. Potom sa porovna ake je perioda, teda to N. to N je koncove (v cykle) i++

Nebudem namietat, ved ten algoritmus sa uz neda nijak vylepšit, čo do rýchlosti.

Ak to nie je prvočíslo, tak nie je splnená podmienka bodu 3. A dokedy má v cykle pokračovať? Neviem, či mám chybu v programe, ale do bodu 3 sa nedostanem, ak to nie je prvočíslo, ale veľké číslo.

cyklus robis do max N=(p-1)/2

v hodnote i=N musí platit pre prvočíslo usporiadana dvojica (m,n)=(p,0) alebo (4,p-4), ak nie je to zmiesane číslo.

Zmiešane čísla maju kratšie periody, ak sa počas beehu cykluz vyskytne dvojica (p,0) alebo (4,p-4), tak ide o zmiešane čislo, program našiel kratšiu periodu.

Ak narazis, že sa neobjaví vobec táto hodnota, potom ide o zmiesane číslo a vysvetlenie je to, že sa odrazil cyklus od inej hodnoty. To by chcelo vymysliet jednoduchy sposob ako zachytit tieto kratsie periody, ktoré ani nepristanu na hodnote (p,0) alebo (4,p-4).

Poznamka: špecialne prvočísla sú v tvare p=2^k+1, alebo p=2^k-1,    k=1,2.....

pre p=2^k+1 je perioda T=2k

pre p=2^k-1 je perioda T=k

teda sú to oveľa kratšie periody ako štandartne prvočísla majú.

príklad:

p=25, v hodnote i=12 ma mať (25,0) alebo (4,21). No nemá, jej perióda sa odráža o niečo skor na čísle i=10 dosiahla hodnotu (4, 21)

Ja som ale nenašiel číslo, ktoré by nedospelo k hodnote (p,0) alebo (4, p-4) do periódy (p-1)/2.

Takže tam maš asi nejakú chybu nie?

Huston Huston máme problém, lebo som našiel aj ine periódy :
 napr.

p=113 ma periodu 14. Tu začína ta krása Tono, aby som ta nezaviedol, tak som objavil aj ine periódy, vieš ale čo majú všetky spoločné (periódy prvočísiel)

pred 40 minútami, robopol napísal:

Takže tam maš asi nejakú chybu nie?

Je to možné, pravdepodobne s typom premenných. Skús otestovať prvočíslo 8209 v Excely a pošli mi pár hodnôt  m, n  pred ukončením, nech to skontrolujem. Mne ho program nenájde.

pred hodinou, Tono napísal:

Je to možné, pravdepodobne s typom premenných. Skús otestovať prvočíslo 8209 v Excely a pošli mi pár hodnôt  m, n  pred ukončením, nech to skontrolujem. Mne ho program nenájde.

našlo na i=4104, teda (8209-1)/2. Našlo aj na i=2052. To znamená ma kratšiu periódu, to je podobne ako u 113. Ma kratšiu periodu. teda tu zas prišiel problem pseudoprvočísiel. Ach jo. To som nečakal, že najde aj iné periódy kratšie ako (p-1)/2 a ja nebudem vediet, či to je 100% prvočíslo.

PS: Skúšam domnienku, že prvočísla majú kladné násobky periód, na rozdiel od pseudoprvočísiel. preverene sú pesudoprvočísla, ktoré majú aj párny počet periód do (p-1)/2.

Tono,

Na jednej strane je to výhoda, ,algortimus nemusí bežat do N=(p-1)/2. Postačuje, ked preverí či je celočíselný násobok teda platí N/perioda=integer. Tu potom vieme, že máme prvočíslo, alebo pseudoprvočíslo. Na druhej strane som sa mylne domnieval, že sú len špeciálne prvočísla s kratkymi periodami. Tvoje číslo ma periodu =2. 113 číslo má periodu 2x, resp.4x. preveroval som pár pseudoprvočísiel a tam boli periódy cez 10x. teda pomerne krátke periódy číslo 341-34 násobok,561-14 násobok, 1387-77 násobok.

Toto by bolo najlepšie preverit programom ako sa správajú tie pseudoprvočísla.

tu je list pseudoprvočísiel.

https://oeis.org/A001567

taka hypotéza zatial je ta:

okrem period pre špecialne prvočísla (vid. odkaz) považujme za prvočísla všetko to čo spĺňa podmienku: N/perioda<10, tu je určite extremne vysoka pravdepodobnosť, že program označí prvočíslo.

Program si môžeš nahrať zhttps://drive.google.com/file/d/1P0F7JJTmxEyFLq3TeNB5cRVgT3myt-7X/view?usp=sharing

Spravil som program pre testovanie tvojho algoritmu, (v programe Button Test1)

bool TForm1::Test()
{
 p = atof(Edit_p->Text.c_str());

 Form1 -> old_m = 1;
 Form1 -> old_n = p - 1;

 for(i = 1; i <= (p-1)/2+1; i++)
  {
   if((old_m % 2) == 0)
    {
     m = (old_m + 2)/2;     // Parne
     n = p - m;
    }
   else
    {
     n = (old_n - 2)/2;     // Neparne
     m = p - n;
    }

   // Test ukoncenia
   if(((m == p) && (n == 0)) || ((m == 4) && (n == p - 4)))
    {
     if(i+1 == (p-1)/2)
      {
       return(true);
      }
    }

   old_m = m;
   old_n = n;

  if(i == 0)
   {
    return(false);
   }
  }
 return(false);
}

A algoritmu podľa https://www.algoritmy.net/article/38/Elementarni-test (v programe Button Test2)

bool TForm1::Test2()
{
 p = atof(Edit_p->Text.c_str());

 if(p <= 1)
  return false;

 if(p == 2)
  return true;

 if(p % 2 == 0)
  return false;

 for(int i = 3; i <= sqrt((double)p); i += 2)
  {
   if(p % i == 0)
    return false;
  }

 return true;
}

Tvoj algoritmus je pomalší, lebo prebieha cez (p-1)/2 a ten  v odkaze iba cez sqrt((double)p).

dik za algoritmus, už ti to teda funguje? V čom si mal problém. Samozrejme ak budeš každé číslo prechádzat do (p-1)/2 bude to dramaticky pomalšie.

Ako píšem nižšie nemusí nutne ísť až do (p-1)/2. Existujú aj kratšie periódy.

PS: V odkaze pre program je niečo ine.

Trochu som program upravil, ak chces nahraj si ho znovu. V Excely si pre prehladnost naplnal bunky m,n, Ale nie je to nutne, staci stara a nova hodnota m,n. Takto si mozes v Excely otestovat aj velke cisla.

Ved ano excel je iba pomocnik, mne neslo o rýchlost. ten algoritmus, čo tu je (dik za snahu) je uplne na hrubo nasekany, keby si zohladnil všetky veci co tu su, tak je dlhsi aj efektivnejsi.

Napr. hodnotu nasledneho m budes ratat iba vtedy ked aj predchadzajuce m je parne, to plati aj pre n. To je jedna uspora. Druha dramaticka uspora je v tom, že ty v cykle musis zastavit na prvom (p,0) alebo (4,p-4) a nasledne porovnat hodnotu i=perioda,  N=(p-1)/2 potom pre prvočíslo plati N/perioda =integer, pre zložene to je destainne číslo.

Prvočísla sú takou "suchou matematikou", ktorá ma veľmi neoslovuje. Celkom nechápem, prečo ich ešte nie je dosť pre kryptovanie, ktoré sa môže dynamicky meniť v čase. To potom nemá žiadny počítač šancu. Keby aj našiel tie prvočísla, dávno by už neplatili. Podobne, ako kód prevodu v banke má obmedzenú časovú platnosť. Spomína sa aj nejaká spojitosť prvočísel s kvantovou fyzikou, ale neviem aká?    

Neviem presne, ale kvantový počítač napr. rieši bludisko tak, že ide paralelne v kazdom smere na krizovatkach, pricom klasicky pc (algoritmus), by preveril jednu vetvu potom druhu atd. Suvisí to nejak so superpozíciou stavov. Obdobne by si to vedel aplikovat na hladanie prvočísiel.

Vieš, čo by mi viac pomohlo, keby si to urobil pre ten dlhy format čísiel, to by som musel hladat ako na to. napr. vyrátat obrovskú mocninu zapísat číslo - nejako. Ten algoritmus sa dá značne vylepšiť a hlavne použiť na Mersenove čísla ibaže inak ako je toto.

pred 8 minútami, robopol napísal:

Neviem presne, ale kvantový počítač napr. 

Ak sa to podarí, tak je koniec s RSA. To by bol riadny chaos. To by museli byť kvantové počítače ale komerčne úspešné. Takže by pravdepodobne fungoval aj prenos pomocou previazaných stavov a kryptovanie by bolo zbytočné.

Ano s nástupom kvantových počítačov sa musí zmeniť šifrovanie, alebo prejst na tak vysoke prvočísla, že to nevyráta ani kvantový počítač. Problem, ale skôr vidím s uložením takého obrovského čísla, čo sú dáta, takže skorr sa musi zmeniť šifrovanie za kvantové.

pred 48 minútami, robopol napísal:

alebo prejst na tak vysoke prvočísla, že to nevyráta ani kvantový počítač. Problem, ale skôr vidím s uložením takého obrovského čísla

Ja to nechápem. Podla Eulera,  počet prvočísiel menších ako m je m/ln(m); Takže ak si zvolíme 500 miestne prvočíslo, tak máme pre kódovanie RSA k dispozícii .1000000000e499 dvojíc prvočísel. To je nepredstaviteľné číslo. Odhaduje sa, že v galaxii sú stovky miliard hviezd a vo vesmíre stovky miliard galaxií. Ak som sa nepomýlil tak nech je to cca 10e25 hviezd. Lenže my máme exponent 498. A 500 miestne prvočíslo zaberie v dnešnej dobe zanedbateľné miesto. A vygenerovať ho v mojom PC trvalo iba desiatky sekúnd. Nabúrať sa do systému je skôr otázkou chyby v programe, alebo obsluhe.

Tonu skusal som ten debug programu, nefunguje to: vyhadzuje len hlasku: neni zadane číslo.

Skus tam doplnit tie dve veci:

zadefinuj N=(p-1)/2,

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.

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

pred 12 minútami, robopol napísal:

Tonu skusal som ten debug programu, nefunguje to: vyhadzuje len hlasku: neni zadane číslo.

Ano mám tam chybu, za chvílu to opravím.

ale urob tam tie dva body, pretože to si ho značne spomalil, to je jasne, že v takej podobe ako je horsi. NAvyše si si možno vybral čísla, ktoré majú práve dlhe periody, je kopu krátkych period.

do kolonky pre vstup p=číslo, nedavaj len nejake vybrane hodnoty, to nema zmysel

Uz by mal ten odkaz fungovat na opravený subor.

odkaz ešte nefunguje, však maš čas nehori:)

Predstav si zložene číslo napr 6 miestne, nepárne (1,3,7,9) tak si predstav, že perioda može byt aj 1000 a program zastavi, takto ti prechádza každé číslo do polovice čísla, to si nemusel testovat :)

pred 7 minútami, robopol napísal:

odkaz ešte nefunguje, však maš čas nehori:)

Default je okno pre zadanie p prázdne. Musíš tam zadať nejaké číslo, ktoré chceš testovať, alebo si vybrať z ponuky prvočísel, ktorá je v spodnom okne. Alebo mám v odkaze zmätok? Skús to a odpovedz mi.