Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica RAZNO PSEUDOMATEMATIKA

Test za proste brojeve

Radovi za koje se tvrdi da su matematički, ali nemaju rigorozan dokaz.
(Ne ulazite ako imate slab želudac! :) )

Test za proste brojeve

Postod primus » Ponedeljak, 03. Februar 2020, 05:04

Konjektura
Neka je [inlmath]n[/inlmath] prirodan broj veći od dva. Neka je [inlmath]r[/inlmath] najmanji neparan prost broj takav da [inlmath]r\not\mid n[/inlmath] i [inlmath]n^2\not\equiv1\pmod r[/inlmath]. Neka je [inlmath]T_n(x)[/inlmath] Čebiševljev polinom prvog reda, tada je [inlmath]n[/inlmath] prost broj ako i samo ako je [inlmath]T_n(x)\equiv x^n\pmod{x^r-1,\,n}[/inlmath].


Test možete isprobati ovde (Conjecture 5).
Test je verifikovan za sve [inlmath]n<10^{10}[/inlmath]. Vreme izvršenja algoritma u najgorem slučaju je [inlmath]\Theta\left(\log^3n\right)[/inlmath].

PARI/GP program (imenujte skriptu: Test.gp):

Kôd: Obeleži sve
xmat(r,n) = {[2*x, -1; 1, 0]*Mod(1,x^r-1)*Mod(1,n);}
smallestr(n)={if(n==1 || n%2==0, return(0));forprime(r = 3,oo,my(u=n%r);if (u==0 && r < n, return(0));if (u!=0 && u!=1 && u!=r-1, return(r)));}
myisprime(n)={my(r = smallestr(n));if (r == 0, return(n == 2));my(xp = xmat(r,n)^n*[x,1]~);xp[2] == Mod(x*Mod(1,n),x^r-1)^n;}
Test(n)={if(myisprime(n),print("Prime!"),print("Composite!"))}
Korisnikov avatar
primus  OFFLINE
 
Postovi: 42
Zahvalio se: 3 puta
Pohvaljen: 44 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Test za proste brojeve

Postod ubavic » Sreda, 05. Februar 2020, 17:40

Konjektura deluje veoma zanimljivo. Imaš li možda ideju kako bi se ovo dokazalo?

Jedno pitanje imam: Šta tačno označava [inlmath]\pmod {x^r-1,n}[/inlmath]?
Korisnikov avatar
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 541
Lokacija: Zrenjanin
Zahvalio se: 350 puta
Pohvaljen: 530 puta

  • +1

Re: Test za proste brojeve

Postod primus » Sreda, 05. Februar 2020, 18:47

Zaista nemam ideju kako bi se ovo moglo dokazati. Što se tiče tvog pitanja pogledaj ovde u koraku broj 5 definiciju funkcije: PolyModulo[f_] .
Korisnikov avatar
primus  OFFLINE
 
Postovi: 42
Zahvalio se: 3 puta
Pohvaljen: 44 puta


Povratak na PSEUDOMATEMATIKA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 1 gost


Index stranicaTimObriši sve kolačiće boarda
Danas je Subota, 29. Februar 2020, 02:24 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs