Hot answers tagged

26

Yes, PRIMEGAME outputs $2^k$ if and only if $k$ is prime. Conway's original paper is well worth reading if you can track it down. You can also find a very clear exposition in Richard Guy's paper Conway's prime producing machine (Mathematics Magazine 56(1):26–33, 1983), including the wonderful cartoon below. (Yes, that's Conway with the Alexander horns, ...


19

The question is, in my opinion, quite vague and involves some misunderstanding, so this answer attempts only to provide the right vocabulary and point you in the right direction. There are two fields of computer science that directly study such problems. Inductive inference and computational learning theory. The two fields are very closely related and the ...


12

The success of a learning algorithm depends critically on the representation. How do you present the input to the algorithm? In an extreme case, suppose you present the numbers as sequences of prime factors -- in this case, learning is quite trivial. In another extreme, consider representing the numbers as binary strings. All the standard learning algorithms ...


9

No, the intuitive observation "There are about $\sqrt{n}$ prime factors to try" does not imply a lower bound on the complexity of factoring. There is absolutely no reason that a factoring algorithm must try every possible prime factor, or even that the algorithm's behavior should resemble "trying" different factors at all. Even though precisely the same ...


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 ...


3

In a related not-quite answer to @jagadish's, after being defined, Costas arrays were quickly found for very small numbers, and were later found for sizes $p-1$, where $p$ is prime. However, it is open whether they exist for all $n$ and computer searches are making people believe that they do not exist for $n=32$.


3

Note: This is more like an extended comment than an answer. Here is a problem from combinatorics whose status is similiar in flavor to that of Evasiveness Conjecture: Background. A Latin square of order $n$ is an $n × n$ matrix in which each element from {1, . . . , n} occurs exactly once in each row and column. Two Latin squares of order $n$ are said to ...


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