The tag has no usage guidance.

learn more… | top users | synonyms

-2
votes
1answer
115 views

A curious statement in an old blog

In http://blog.computationalcomplexity.org/2009/08/finding-primes.html, a statement is added which reads "Oddly enough we would usually prefer a probabilistic over the deterministic method to find ...
5
votes
0answers
120 views

Implications of a deterministic polytime prime-finding algorithm

I'm wondering what are the current known uses/implications of a polynomial-time algorithm for the following problem: Given $n$ in binary, output a prime $p > n$. I'm both curious about ...
9
votes
2answers
412 views

Why does most cryptography depend on large prime number pairs, as opposed to other problems?

Most current cryptography methods depend on the difficulty of factoring numbers that are the product of two large prime numbers. As I understand it, that is difficult only as long as the method used ...
6
votes
2answers
298 views

Does “Productive function” mean just that in ME O'Neill, The Genuine Sieve of Eratosthenes?

M.E. O'Neill in the Epilogue of "The Genuine Sieve of Eratosthenes" (preprint http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf DOI 10.1017/S0956796808007004) quotes Richard Bird that "union is ...
11
votes
2answers
678 views

What's the most efficient algorithm for Divisibility?

What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
1
vote
3answers
4k views

Why can machine learning not recognize prime numbers?

Say we have a vector representation of any integer of magnitude n, V_n This vector is the input to a machine learning algorithm. First question : For what type of representations is it possible to ...
17
votes
2answers
353 views

What are TCS conjectures that were proved for primes and small values but then turned out to be false?

Are there any conjectures in theoretical computer science that involve some parameter n and were proved for small values of n AND for primes but later turned out to be false? In number theory such ...
-2
votes
1answer
326 views

Computational complexities in factoring

[Note: n is a given integer (not the number of its digits)] I'd like to know how O(sqrt(n)/log(n)) would compare against the computational complexity of the best available algorithms (as well as the ...
16
votes
1answer
696 views

Does Conway's PRIMEGAME generate all prime powers of 2?

Most sites I have visited reading on this interesting topic state something along the lines "the only powers of two (other than 2 itself) that occur in this sequence are those with prime exponent" ...
4
votes
0answers
155 views

Complexity of computing logarithm of a prime power

Suppose $n = p^k$ for some prime number $p$ and some non-negative integer $k$. What is (the best-known upper bound on) the complexity of computing $k$ on input $n$ (given in binary)? It is important ...
-1
votes
1answer
76 views

Rabins Signature Implementation [closed]

I am searching for an Implementation for Rabins Algorithm in any language. I've searched but haven't got it anywhere. does anybody have a link ?
34
votes
2answers
2k views

Are the problems PRIMES, FACTORING known to be P-hard?

Let PRIMES (a.k.a. primality testing) be the problem: Given a natural number $n$, is $n$ a prime number? Let FACTORING be the problem: Given natural numbers $n$, $m$ with $1 \leq m \leq n$,...
0
votes
2answers
268 views

How to calculate the cost of factoring a large integer?

I would like to know how much it would cost to factor a large integer. The cost can be given computer operations, time to process it or even monetary value. I know there are people that factored 200 ...
12
votes
0answers
254 views

Conditional density of primes

We have some theorems about the density of prime numbers, the most famous one is probably the prime number theorem. My question is about the density of primes when we choose random numbers from ...
23
votes
2answers
890 views

Finding a prime greater than a given bound

Is a deterministic polynomial-time algorithm known for the following problem: Input: a natural number $n$ (in binary encoding) Output: a prime number $p > n$. (According to a list of open ...