Questions tagged [primes]
The primes tag has no usage guidance.
29
questions
1
vote
0
answers
66
views
What would be the cost to factor a 1024‒bits RSA modulus most economically within months today?
Of course this is a question with an answer that is due to evolve.
A 2002 paper about TWIRL stated that the cost would be around 10M$$ and an other 10M$ to manufacture the devices. A later 2007 paper ...
6
votes
2
answers
626
views
NP-complete problems where the inputs are prime numbers
Are there (well?) known NP-complete problems where the input(s) is(are) a(some) prime number(s), with complexity measured relative to the binary length of the input number(s)? I am thinking there are ...
-3
votes
1
answer
136
views
help me understand what semiprime factorizations are worth
Based on a response I received in another post, I would like to ask this question.
Are there semiprimes that are not very interesting in terms of research and are not worth factoring?
Are only the RSA ...
-3
votes
2
answers
185
views
pq factorization
If I tried to factor a semiprime as the product of the two prime factors given below in the form pq on a home computer would I be successful?
p=(2^1024-1)+644 prime factor
q=(2^1028-1)+188 prime ...
3
votes
0
answers
99
views
Complexity of checking if a given prime number can be computed using at most $s$ addition/multiplication operations?
Given are a prime number $p$ and a parameter $s\in\mathbb{N}$.
What is the computational complexity of the problem of determining whether $p$ is computable by a series of at most $s$ steps, each being ...
2
votes
1
answer
210
views
Is Levin's Universal Search valid for the integer factorization problem while using the AKS test?
It seems that there are many versions of this question that have answers when I look it up. But it seems quite clear that LUS should find a factor within an asymptotically quadratic transformation of ...
1
vote
1
answer
75
views
Would the following be an acceptable part of an algorithm if used for prime factorization
Suppose I have some super fancy algorithm for prime factorization. I want to demonstrate its potential on a difficult case, like an RSA sized number composed of two primes,$\space n=p_1p_2$. As far as ...
2
votes
0
answers
108
views
How to generate arbitrarily in-order from a set of primes?
Given an ordered array of distinct prime numbers $p_{i, 1 \le i \le n}$ and a number $m$, can you calculate the $m$th natural number generated by $p$? I need something optimized preferably logarithmic ...
9
votes
1
answer
492
views
Formalizing the "no formula for primes" intuition
I was trying to formalize the intuition is that there is no formula for primes, and this is my best attempt:
Conjecture: There is no $O(n^2)$ expected time randomized algorithm to generate $\ge n$-...
20
votes
1
answer
509
views
Is prime-counting function #P-complete?
Recall $\pi(n)$ the number of primes $\le n$ is the prime-counting function. By "PRIMES in P", computing $\pi(n)$ is in #P. Is the problem #P-complete? Or, perhaps, there is a complexity reason to ...
1
vote
0
answers
66
views
Anagrams, Prime numbers and prime coding [closed]
I am from math.stackexchange, here is my original post.
https://math.stackexchange.com/questions/2354828/anagrams-prime-numbers-and-prime-number-coding
The only comment I received was too technical ...
3
votes
0
answers
271
views
Primality in $NC$ hierarchy?
AKS primality testing solves whether a given integer is prime in $P$. AKS algorithm is following:
Input: integer n > 1.
Check if $n$ is a perfect power: if $n = a^b$ for integers $a > 1$ and $b &...
5
votes
0
answers
147
views
How hard is it to generate a set of relatively prime numbers between two given bounds?
Informal Question
How hard is it to generate a set of relatively prime numbers between two given bounds?
Decision Problem
Given $a$, $b$, and $k \in \mathbb{N}$. Does there exist a set $S \...
8
votes
0
answers
303
views
Algorithms to generate consecutive primes
The prime number theorem, states that the "average length" of the gap between a prime $p$ and the next prime is ln(p). I am looking for (preferably deterministic efficient) an algorithm that generates ...
-2
votes
1
answer
147
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
0
answers
133
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 specific ...
9
votes
2
answers
667
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
2
answers
446
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 ...
13
votes
2
answers
2k
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 ...
15
votes
5
answers
15k
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
2
answers
411
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
1
answer
407
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 ...
17
votes
1
answer
1k
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
0
answers
187
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
1
answer
84
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 ?
42
votes
2
answers
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$, ...
1
vote
2
answers
336
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
0
answers
278
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 a ...
28
votes
2
answers
1k
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 ...