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!"))}
Plenus venter non studet libenter
Korisnikov avatar
primus  OFFLINE
 
Postovi: 232
Zahvalio se: 15 puta
Pohvaljen: 278 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]?
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 623
Zahvalio se: 385 puta
Pohvaljen: 641 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_] .
Plenus venter non studet libenter
Korisnikov avatar
primus  OFFLINE
 
Postovi: 232
Zahvalio se: 15 puta
Pohvaljen: 278 puta


Povratak na PSEUDOMATEMATIKA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 23 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 10:13 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs