Ist es möglich, eine * größer als * -Funktion nur durch Addition, Subtraktion und Multiplikation zu implementieren?

7

Alle Werte stammen aus einem endlichen Feld Zt. Ich möchte eine größere Funktion als diese schreiben

GT(x,y)={1,if x>y,0,otherwise.

Verwenden Sie nur Additionen, Multiplikationen, Subtraktionen und vorzugsweise keine Divisionen.

Die Gleichheitsfunktion

EQU(x,y)={1,if x==y,0,otherwise.

kann so berechnet werden

EQU(x,y)=1(xy)p, wobei p die Euler-Totientenfunktion ist p=phi(t)=t1 da t ist Prime.

Kann eine Funktion größer als auf ähnliche Weise geschrieben werden?

Die Funktion größer als würde für eine homomorphe Verschlüsselungsanwendung verwendet , um den maximalen Ganzzahlwert aus einem Vektor verschlüsselter Ganzzahlen zu ermitteln.

user2991856
quelle
Ihre letzte Gleichung funktioniert nicht. (Versuch mal x und y , die von mehr als 1 unterscheiden)
6
Auf endlichen Feldern gibt es kein vernünftiges Größeres .
k.stm
@ RickyDemer Es funktioniert, wenn man ersetzt t durch t1In einem finiten Feld: , für alle mit , ist . tαtα0αt1=1
k.stm
1
Ich möchte die Funktion größer als für einen homomorphen Vergleich zwischen Nachrichten aus einem Raum Z_t verwenden, wobei t größer als 2 ist. In Abschnitt 3 dieses Dokuments ist acad.ro/sectii2002/proceedings/doc2015-3s/08-Togan.pdf gegeben das Polynom für größer als Funktion für Binärwerte. Ich möchte die gleiche Funktionalität, aber für ganzzahlige Werte, wenn es möglich ist, berechnet zu werden.
user2991856
3
Was hat das mit CS zu tun? Warum ist das nicht bei MathOverflow oder Mathematik ?
Katze

Antworten:

13

Jede Funktion auf einem endlichen Feld kann als Polynom individuellen Grades höchstens eindeutig dargestellt werden .GF(q)q1

Wie Sie bereits erwähnt haben, ist Ein Polynom, das genau dann gleich ist, wenn . Daher können wir jede Funktion in den Variablen in der folgenden Form darstellen: Da die Dimension des Raums von variablen Funktionen und die Anzahl der Monome von höchstem Grad ebenfalls , schließen wir, dass diese Darstellung eindeutig ist.1xq1=[[x=0]]1x=0f:GF(q)nGF(q)x1,,xn

t1,,tnGF(q)f(t1,,tn)i=1n(1(xiti)q1).
nqnq1qn
Yuval Filmus
quelle
huh? scheint die Frage nicht zu beantworten. es scheint in gewissem Sinne zu behaupten, dass alle Funktionen konstruiert werden können ... aber es scheint nicht zu beschreiben, wie man sie konstruiert (eine bestimmte oder die angeforderte) ...
vzn
1
@vzn Wenn alle Funktionen konstruiert werden können, kann jede einzelne sein.
Yuval Filmus
Die Funktionsbeschreibung für größer als wäre sehr dankbar, da ich nicht herausgefunden habe, wie man sie erstellt.
user2991856
1
Ich gebe eine Formel , die für jede Funktion arbeitet . Sie müssen nur Ihre Funktion ersetzen . Das Ergebnis wird nicht unbedingt schön sein, aber es wird ein Polynom sein, das Ihre Funktion berechnet. ff
Yuval Filmus
Vielleicht gibt es jedoch keine Funktion, die ein vernünftiges für berechnet . Wir werden das erst wissen, wenn wir uns auf eine Definition festgelegt haben. >GF(q)
Rick Decker