NTRU

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

NTRU

Beitrag von DMT » 3. Mär 2009 14:50

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 » 3. Mär 2009 16:10

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 » 3. Mär 2009 16:27

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 » 3. Mär 2009 16:50

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 » 3. Mär 2009 19:25

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“