Hot answers tagged

9

I'm not sure this is a statement about primes so much as it is a statement about secret key generation: if the method is deterministic (e.g. take the smallest prime larger than 10^20), then your adversary can simply reproduce the computation to find your secret key.


9

Boaz Barak addressed this in a blog post My takeaway from his post (roughly speaking) is that we only know how to design cryptographic primitives using computational problems that have some amount of structure, which we exploit. With no structure, we don't know what to do. With too much structure, the problem becomes efficiently computable (thus useless ...


7

Is that the technical term referring to productive sets and creative sets, or is it just a manner of speaking? Neither, actually -- it's a different technical term. The type of streams of natural numbers can be interpreted as the final coalgebra for the functor $F(X) \triangleq \mathbb{N} \times X$. That is, define the category of $F$-algebras as follows: ...


7

Productive here just means that it isn't stuck. An unorthodox (seemingly impredicative ) formulation of the sieve of Eratosthenes is       S = {n : n ∈ N, n > 1} \ ⋃p ∈ S { p q : q ∈ N, q ≥ p } The following code is stuck, reflecting the above definition more or less verbatim: primes = gaps 2 $ foldr (\p r-> ...


7

[Certainly not a complete answer, but too long for a comment] Testing whether a given DFA accepts the base-2 representation of at least one prime number is not known to be computable. If it were uncomputable, that's some kind of weak evidence that there's no "regular-ish" formula for primality. (I mean, we know the set of primes itself is not regular, but ...


6

All of what I am going to say is well-known (all the links are to Wikipedia), but here it goes: The approach used in RSA using pairs of primes can also be applied in a more general framework of cyclic groups, notably the Diffie-Helmann protocol that generalizes $\left(\mathbb{Z}/pq\mathbb{Z}\right)^{\times}$ to an arbitrary group, notably elliptic curves ...


4

Fleshing out my comments into an answer: since divisibility is (trivially) reducible to division, and since division is (nontrivially) reducible to multiplication via approaches like Newton's method, then your problem should have the same time complexity as integer multiplication. AFAIK, there are no known lower bounds for multiplication better than the ...


2

Some heuristic evidence: to the best of our knowledge $\pi(n)$ looks like a simple function corrected by random fluctuations. Thus I’d expect a poly-time machine with a $\pi(n)$ oracle to be no stronger than such a machine with a random oracle, and w.r.t. a random oracle $X$ adding a separate random oracle $Y$ to $\mathsf{P}$ gives $\#\mathsf{P}^X \not\...


Only top voted, non community-wiki answers of a minimum length are eligible