NTRU

DMT
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 18. Dez 2007 23:54

NTRU

Beitrag von DMT »

Hallo,
wie kann man bei der Excerise 3, Task 1 b) das g berechnen?
Weil wir NFAILEN grade ziemlich bei der Aufgabe...

Und es wäre immer noch gut zu wissen, warum wenn beim Buchberger Algo als Rest ein konstantes Polynom rauskommt, wir aufhören können?
"Quis custodiet ipsos custodes?"
~Juvenal

Sho
Erstie
Erstie
Beiträge: 12
Registriert: 19. Feb 2005 23:07

Re: NTRU

Beitrag von Sho »

Es gilt: \(h=p*f_q*g \mod q \Rightarrow f*h = p*(f*f_q)*g \mod q \Rightarrow_{f*f_q\equiv 1mod q} f*h=p*g\mod q\Rightarrow_{p_q*p\equiv 1mod q} p_q*f*h=g\mod q\)
Eingesetzen ergibt: \(f*h=2x^7-3x^6+6x^5+3x^4-2x^2+6x+7\equiv 3x^4+3x+13\mod (x^5-1)\).
\(p_q=-5\equiv 11\mod 16\)
\(g=-15x^4-15x-65\equiv x^4+x-1 \mod 16\)

rueckert
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 9. Apr 2008 09:25

Re: NTRU

Beitrag von rueckert »

Wenn ich die Frage zu Buchberger richtig verstehe, ist die Antwort:

ein konstantes Polynom a kann man immer zum Polynom 1 machen. Sobald 1 in der Idealbasis ist, kann man alle anderen vergessen, denn <1> = R.

Sho
Erstie
Erstie
Beiträge: 12
Registriert: 19. Feb 2005 23:07

Re: NTRU

Beitrag von Sho »

rueckert hat geschrieben:ein konstantes Polynom a kann man immer zum Polynom 1 machen. Sobald 1 in der Idealbasis ist, kann man alle anderen vergessen, denn <1> = R.
Ich bekomme bei Ex.4,T.4 a)(ii) \(S(f,g)= -3\) raus. Trotzdem ist \(G\ne R\) :(

rueckert
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 9. Apr 2008 09:25

Re: NTRU

Beitrag von rueckert »

An die -3 kann ich mich erinnern. Die minimale Gröbnerbasis müsste also {1} sein. Da ihr nicht minimieren oder sonst irgendwie optimieren solltet, wurde auch in der Lösung nur ein Zwischenergebnis angegeben.

Antworten

Zurück zu „Archiv“