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

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

$GT(x,y) = \begin{cases} 1, & \text{if } x > y, \\ 0, & \text{otherwise}. \end{cases}$

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

Die Gleichheitsfunktion

$EQU(x,y) = \begin{cases} 1, & \text{if } x == y, \\ 0, & \text{otherwise}. \end{cases}$

kann so berechnet werden

$EQU(x,y) = 1 - (x-y)^p$ , wobei p die Euler-Totientenfunktion ist $p=phi(t)=t-1$ 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.

algorithms linear-algebra user2991856
quelle

Ihre letzte Gleichung funktioniert nicht. (Versuch mal x und y , die von mehr als 1 unterscheiden)

Auf endlichen Feldern gibt es kein vernünftiges Größeres .

k.stm

@ RickyDemer Es funktioniert, wenn man ersetzt

t

$t$ durch

t - 1

$t-1$ In einem finiten Feld: , für alle mit , ist .

ℤ_{t}

$ℤ_t$

α \in ℤ_{t}

$α ∈ ℤ_t$

α \neq 0

$α ≠ 0$

α^{t - 1} = 1

$α^{t-1} = 1$

k.stm

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

Was hat das mit CS zu tun? Warum ist das nicht bei MathOverflow oder Mathematik ?

Katze

Antworten:

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

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. $1-x^{q-1} = [\![x=0]\!]$ $1$ $x=0$ $f\colon GF(q)^n \to GF(q)$ $x_1,\ldots,x_n$

\sum_{t_{1}, \dots, t_{n} \in G F (q)} f (t_{1}, \dots, t_{n}) \prod_{i = 1}^{n} (1 - (x_{i} - t_{i})^{q - 1}) .

$\sum_{t_1,\ldots,t_n \in GF(q)} f(t_1,\ldots,t_n) \prod_{i=1}^n \left(1-(x_i-t_i)^{q-1}\right).$

n

$n$

q^{n}

$q^n$

q - 1

$q-1$

q^{n}

$q^n$

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

@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

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.

f

$f$

f

$f$

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.

>

$>$

G F (q)

$GF(q)$

Rick Decker