Questions tagged [polynomial]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
2 answers

Probabilistic proof of multiplying two elements from non-prime finite field

I was reading this paper, and there, they use the ring $\mathbb{Z}_{\large p}[\alpha]/(\alpha^{\large n}+1)$ for all their operations. And that looks like a construction of finite field $\mathbb{F}_{\...
the thinker's user avatar
0 votes
0 answers

One-way function constructed by multivariable polynomials

Although the conjecture regarding the existence of one-way functions remained open, there are numerous NP-based methods for constructing diverse one-way functions, including DL, lattice, and subset ...
X.H. Yue's user avatar
  • 368
0 votes
0 answers

What do we mean when we say we need more than polynomial time many cipher texts

What does it mean when we say something like „we need more than polynomial time many cipher texts“? I understand it as „an adversarial can run for polynomial time and try as many messages as possible ...
jilgolfo's user avatar
2 votes
0 answers

Inefficient double-lengthening PRG

I'm trying to prove that an inefficient double-lengthening PRG exists, i.e. construct a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{2n}$ My current approach is to bound the number of poly-time non-uniform ...
Stevie's user avatar
  • 123
0 votes
0 answers

Convert an arbitrary array of integers to super increasing sequence

I have an arbitrary array $X = (x_1, x_2, \dots, x_n)$ of disjoint integers. I want to determine whether there exists a prime number, $p$, and a value $y < p$ such that the sequence $$Y = \left(y_1,...
Lisbeth's user avatar
  • 497