The primes tag has no wiki summary.
4
votes
2answers
141 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 ...
9
votes
0answers
148 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
701 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
320 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
270 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
275 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
124 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
71 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 ?
22
votes
2answers
946 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
229 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 ...
11
votes
0answers
227 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 ...
22
votes
2answers
736 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 ...
