Hausübung Aufgabe 1: g^p' mod p != 1

hanneswernery
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 30. Dez 2012 15:26

Hausübung Aufgabe 1: g^p' mod p != 1

Beitrag von hanneswernery »

Hi

ich habe folgendes Verstädnisproblem.
Bei Aufgabe 1 wählen wir ja am Anfang p=2p'+1, sodass p und p' Primzahlen sind.
Später soll ein g element [2..p-1] gewählt werden mit g^p' mod p != 1. Ich wollte beim Programmieren die Rechnung etwas auseinanderziehen und vereinfachen und genau da liegt mein Problem:

g^p' mod p =
g^((p-1)0,5) mod p =
((g^(p-1))^0,5) mod p =
((g^(p-1) mod p) ^0,5 mod p) mod p =
(1^0,5 mod p) mod p=
1

Ich hoffe es ist lesbar genug. Ich schreibe den Exponenten um, dass ich (p-1) oben habe, dann wende ich Moduloaritmetik Satz 2.1.5 an (a^b mod c = (a mod c)^b mod c) und am Ende den Korollar 2.1.17 vom kleinen Satz von Fermat (a element N und p ist Primzahl: a^(p-1) mod p = 1). Also auf dem Papier kommt dann bei mir immer 1 raus.
Offensichtlich muss da irgendwo ein Fehler sein, ich finde ihn allerdings nicht.

Lg,
Hannes

errt
Mausschubser
Mausschubser
Beiträge: 61
Registriert: 18. Okt 2012 19:12

Re: Hausübung Aufgabe 1: g^p' mod p != 1

Beitrag von errt »

Ich würde mal vermuten, dass du den kleinen Satz von Fermat so nicht anwenden kannst, weil er in dieser Form als Bedingung hat, dass die Basis kein Vielfaches von p ist, was du aber hier nirgends nachweist. Außerdem gilt der Satz 2.1.5 nur für a,b Element Z, dein b ist aber 0.5.

hanneswernery
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 30. Dez 2012 15:26

Re: Hausübung Aufgabe 1: g^p' mod p != 1

Beitrag von hanneswernery »

Das g kein vielfaches von p ist, ist ja durch g element [2..p-1] gegeben.
Es wird am Exponenten liegen, da 0,5 nicht element Z ist:

2^0,5 mod 2 = 1,44.. mod 2 = 1,44..
und nicht
2^0,5 mod 2 = (2 mod 2)^0,5 mod 2 = 0^0,5 mod 2 = 0

Dann hat sich das also erledigt und ich programmier mal los. Danke dir

Antworten

Zurück zu „Archiv“