Seite 1 von 1

NTRU

Verfasst: 3. Mär 2009 14:50
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?

Re: NTRU

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

Re: NTRU

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

Re: NTRU

Verfasst: 3. Mär 2009 16:50
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\) :(

Re: NTRU

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