Questions tagged [primes]

The tag has no usage guidance.

8 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
156 views

Min no.of operations required to convert an array to which it should contain elements of equal frequency

I have come across this tricky problem. An array of N elements should be converted to another array within k operations such ...
2
votes
0answers
80 views

AKS primality test- Lemma 4.3, not following

I'm reading the AKS primality test paper as it is found here. I'm confused about a statement in Lemma 4.3: "Note that $(r, n)$ cannot be divisible by all the prime divisors of $r$ since otherwise $r$...
2
votes
0answers
53 views

Reference Request: Factorization of PseudoPrimes?

Is there any literature/survey/papers/books regarding the factorization of Strong PseudoPrimes (wrt. to a given base). I am aware of the fact that weak Pseudo Primes can be factorized in Polynomial ...
1
vote
0answers
91 views

how did the authors of the AKS-Paper come up with the upper bound for r? and what does the multiplicative order have to do with anything?

I have been recently reading the paper "PRIMES is in P", but unfortunately a lot the steps were skipped, which led to confusion. My main problem is with the upper bound on r which was not explained at ...
1
vote
0answers
345 views

Can the Sieve of Eratosthenes be adapted to find twin primes

The Sieve of Eratosthenes is an algorithm generate the prime numbers, $2,3,5,7,11,13,...$ by drawing a list of numbers crossing out multiples of the smallest number in the list. Is there anyway to ...
1
vote
1answer
62 views

Is SEMIPRIME in P?

The title says it all: is there a deterministic polynomial time algorithm that tests for semiprimality? (A number $N$ is a semiprime if it is the product of two primes.) I don't understand the ''...
0
votes
0answers
28 views

Algorithm always provide a $2$_$sum$ with at least ONE prime? In polynomial-time?

Function Problem: Given $N$ find a $2$_$sum$ that uses at least $ONE$ prime. Fact: Prime Gaps grow logarithmically on average. And, in worst case if memory serves correct it grows with a bounded ...
0
votes
0answers
625 views

Design a Turing Machine Checking if power is prime

I have to design a Turing Machine to do the following, but I don't really know where to start with this question. Any help would be very much appreciated. I should design a Turing Machine accepting ...