The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
2answers
229 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
386 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
votes
3answers
1k 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 ...
16
votes
2answers
336 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
300 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 ...
11
votes
1answer
380 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
142 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
74 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 ?
32
votes
2answers
1k 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 ...
0
votes
2answers
249 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
248 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
816 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 ...