Forums Neueste Beiträge
 

hinreichender Primzahltest für Primzahlen auf quadratischen Polynomen

01/10/2007 - 16:53 von Bernhard Helmes | Report spam
Einen erfreulichen, guten Abend

Ich habe für Primzahlen auf einigen quadratischen Polynome anscheinend
einen hinreichenden Primzahltest gefunden.

These:
Sei p mod 4 = 3 und 2 nichtquadratischer Rest von p.
Wenn 2^[(p-1)/2]=p-1 mod p, dann ist p eine Primzahl.

1. Frage: Welche Polynome eignen sich noch
2. Làßt sich dafür ein Beweis finden.
Die Zahl 2 taucht nie als Teiler der Funktionswerte des Polynom auf.

Prg in MuPad

basis:=2;
anz:=0;
for x from 1 to 100000000 do

// Polynome bei denen ich kein Gegenbeispiel gefunden habe
// p:=x^2+x+1;
// p:=2*x^2+1;
// p:=x^2+3*x+1;
// p:=2*x^2+1;
// p:=2*x^2+2*x-1;
// p:=3*x^2+x+1;
// p:=3*x^2+x-1;
// p:=3*x^2-x-1;
// p:=3*x^2+x+1;
// p:=3*x^2+3*x-1;
p:=3*x^2+x-1;

if (p mod 4 = 3 and numlib::jacobi (basis, p)=-1) then

res:=powermod (basis, (p-1)/2, p);
if res=(p-1) then
anz:=anz+1;
print (anz, p, "is prime", p mod 8);
if isprime (p)úLSE then
print (ifactor (p)," FALSCH");
return ();
end_if;
end_if;

end_if;
end_for;

Freue mich auf Kommentare
Freundliche Grüße von den Primzahlen
Bernhard
 

Lesen sie die antworten

#1 Jan Fricke
03/10/2007 - 11:33 | Warnen spam
Bernhard Helmes wrote:
Einen erfreulichen, guten Abend



Hallo Bernhard, einen guten Morgen!

Ich habe für Primzahlen auf einigen quadratischen Polynome anscheinend
einen hinreichenden Primzahltest gefunden.

These:
Sei p mod 4 = 3 und 2 nichtquadratischer Rest von p.



2 ist genau dann ein nichtquadratischer Rest, wenn es einen Primteiler
von p gibt, der =3,5 mod 8. In Deinen Programm wird nur auf
Jacobi(2,p)=-1 geprüft (was àquivalent zu p=3,5 mod 8 ist), das ist aber
nur eine hinreichende Bedingung dafür. (Gegenbeispiel für "notwendig": 2
ist kein quadratischer Rest mod 9, aber Jacobi(2,9)=1.)

Wenn 2^[(p-1)/2]=p-1 mod p, dann ist p eine Primzahl.



Gegenbeispiel: p = 476971 = 11 * 131 * 331.
Die Umkehrung (p Primzahl => 2^[(p-1)/2]=p-1 mod p) ist natürlich korrekt.

Selbst wenn p eine spezielle Polynomform hat, wird es Gegenbeispiele
geben, die man aber sicherlich nicht mit brachialer Rechengewalt findet.

1. Frage: Welche Polynome eignen sich noch



Wahrscheinlich viele andere, aber...

2. Làßt sich dafür ein Beweis finden.



...es wird sich weder ein Beweis noch ein Gegenbeispiel finden, da die
potenziellen Gegenbeispiele mit Computerhilfe nicht mehr handhabbar sind.

Insofern sind diese Kriterien relativ gute Indikatoren, aber sicher sind
sie nicht.

Freundliche Grüße von den Primzahlen



Viele Grüße zurück ;-)

Jan

Ähnliche fragen