É possível implementar uma função * maior que * usando apenas adição, subtrações e multiplicações?

Todos os valores são de um campo finito . Eu quero escrever uma função maior do que esta $Z_t$

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

usando apenas adições, multiplicações, subtrações e, de preferência, não divisões.

A função de igualdade

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

pode ser calculado assim

$EQU(x,y) = 1 - (x-y)^p$ , onde p é a função totiente de Euler porque é primo. $p=phi(t)=t-1$ $t$

Uma função maior que pode ser escrita de maneira semelhante?

A função maior que seria usada para um aplicativo de criptografia homomórfica para encontrar o valor inteiro máximo de um vetor de números inteiros criptografados.

algorithms linear-algebra user2991856
fonte

Sua última equação não funciona. (Apenas tente x e y que diferem por mais de 1.)

Não há razoável maior em campos finitos.

k.stm

@RickyDemer Funciona, se alguém substituir por : em um campo finito , para todos os com , .

t

$t$

t - 1

$t-1$

ℤ_{t}

$ℤ_t$

α \in ℤ_{t}

$α ∈ ℤ_t$

α \neq 0

$α ≠ 0$

α^{t - 1} = 1

$α^{t-1} = 1$

k.stm

Eu quero usar a função maior que para uma comparação homomórfica entre mensagens de algum espaço Z_t, onde t é maior que 2. Na seção 3 deste artigo, acad.ro/sectii2002/proceedings/doc2015-3s/08-Togan.pdf é dado o polinômio para maior que a função para valores binários. Eu quero a mesma funcionalidade, mas para valores inteiros, se for possível ser calculado.

user2991856

O que isso tem a ver com CS? Por que isso não está no MathOverflow ou Mathematics ?

cat

Respostas:

Toda função em um campo finito pode ser representada como um polinômio de grau individual no máximo . $GF(q)$ $q-1$

De fato, como você mencionou, É um polinômio que é igual a se e somente se . Portanto, podemos representar qualquer função nas variáveis da seguinte forma: Como a dimensão do espaço das funções variadas é e o número de monômios de grau individual no máximo também é , concluímos que essa representação é única. $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
fonte

Hã? parece não responder à pergunta. parece-assert em certo sentido, todas as funções podem ser construídas ... mas não parece descrever como construí-la (um em particular, ou o solicitado) ...

vzn

@vzn Se todas as funções puderem ser construídas, cada uma em particular poderá ser.

Yuval Filmus

A descrição da função para maior que seria muito apreciada, pois ainda não descobri como construí-la.

user2991856

Dou uma fórmula que funciona para todas as funções . Você apenas precisa substituir sua função . O resultado não será necessariamente bonito, mas será um polinômio que calcula sua função.

f

$f$

f

$f$

Yuval Filmus 21/03

Talvez, porém, há não é uma função que calcula um razoável em . Não saberemos disso até que definamos uma definição.

>

$>$

G F (q)

$GF(q)$

Rick Decker