10
votes
2answers
271 views

Is there any infinite set of primes for which membership can be decided quickly?

The AKS algorithm decides whether or not $n$ is prime in time $\tilde{O}((\log{n})^6)$. I am wondering if there is any faster algorithm to determine membership in some infinite set of primes. What I ...
0
votes
1answer
61 views

Count numbers with prime digit

Given a number N I need to find the count of the numbers that have atleast one prime digit (2,3,5 or 7) in it. Now N can be upto 10^18.What is the best approach to solve this problem. Example : Let ...
1
vote
4answers
172 views

The fastest way to count prime number that smaller or equal N

I want to count all prime numbers that existing in N but I don't know how to count. Can any one tell me how to count prime numbers that are smaller than or equal to N in mathematics formal?
1
vote
1answer
41 views

Digit wise modulo for calculating power function for very very large positive integers

I am writing a code to calculate $P^Q$ where $P$, $Q$ are positive integers which can have number of digits up to $100000$. I want the result as $r = P^Q \pmod{10^9+7}$, where $10^9+7$ is a prime ...
2
votes
1answer
71 views

Finding an $n$ such that $n^2 \equiv -1 \mod p$

What is an efficient algorithm to find the first number $n$ such that $n^2 \equiv -1 \mod p$ for a prime $p$, if such an $n$ exists? Is there anything better than the brute-force approach up to $p-1 ...
0
votes
1answer
57 views

AP term multiple of prime number

I am having this equation : (a+(n-1)d)%p=0 Here a and d can go upto 10^18 and p is prime number upto 10^9 . How to find the least value of n here? Example : If ...
1
vote
1answer
40 views

Algorithm for checking Prime Power

Suppose we are given some arbitrary positive integer. How can we check whether the integer is a prime power? Brute force would be very inefficient in this case.
9
votes
0answers
97 views

Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
0
votes
0answers
31 views

A prime connection between two numbers with same prefix

If I know that the number n is prime, is there a fast algorithm to check if 10*n+k is prime, where k is 1, 3, 7 or 9? I mean, an algorithm based on the fact that n is prime. Thanks for help! P.S. : ...
0
votes
1answer
165 views

Maximum Number with this condition satisified

Given an array $A$ of $N$ elements $A[1],A[2],A[3]...A[n]$, I need to find maximum element in the array such that $GCD(G,A[i]) > 1$ for given $G$ and $1\leq i\leq N$. Example : Let we have $N=6$ ...
0
votes
1answer
56 views

finding a unique integer using mod

Consider two different prime numbers $x$ and $y$. Show that the following is true: For every pair of numbers $m$ and $n$ so that $0\le m<x$ and $0\le n< y$, there is a unique integer $q$, where ...
1
vote
1answer
69 views

Probabilistic time algorithm for finding the solution for quadratic congruences (case when p is prime)

I was trying to solve the following equation: $$y = x^2 \bmod p$$ where $p$ is prime. I was trying to find an algorithm that solved this and that was in BPP (I don't think there is one in P). I ...
0
votes
3answers
910 views

Co Prime Numbers less than N

I need to find all the numbers that are Coprime to given N and less than N. N can be as large as 10^9. EXAMPLE : Numbers coprime to 5 are 1,2,3,4 I want an efficient algorithm to do it
0
votes
1answer
75 views

Kth Power Coprime with N

Given two integers $N$ and $K$. A function of $N$ and $K$ the sum of K'th powers of the positive numbers, which are coprime with N and also not greater than N. E.g., the Function value for $N=6$ and ...
6
votes
1answer
169 views

What is the big picture behind AKS algorithm?

Despite a number of question on AKS algorithm here, there does not seems to anything related to the idea behind it (for those who don't know, AKS primality testing is found in PRIMES is in P). I read ...
-1
votes
1answer
88 views

How to determine the prime numbers? [closed]

What is the best way to determine the prime numbers? Is there a way other than trial-and-error to determine them? Is the set of prime numbers finite or infinite?
1
vote
0answers
78 views

Is there a proof that Encrypting and then Decrypting any data using AES 256 will result in the same data?

I use AES quite often at work (I'm a software programmer) and I trust that it "works" without understanding the maths behind it. It's a black box to me. Does a mathematical proof exist that AES 256 ...
0
votes
1answer
89 views

Public and private RSA keys, using the primes $p = 5$ and $q = 11$

Assume that $p = 5$ and $q = 11$, and all other variables are defined as per the RSA theorem (a) Suppose we consider $e = 3$. Would $(e, n)$ be a suitable public key? (b) Prove that if $d = 27$, ...
1
vote
1answer
32 views

How to find all natural $x$ that make $x^{15} \equiv -1 \mod p$, where $p$ is prime and x<p

For a given prime $p$, how do I find all natural $x$ that make $x^{15} \equiv -1 \mod p$, where $p$ is prime and x < p? The problem is that trying thoroughly every $x < p$ is too inefficient. I ...
0
votes
1answer
216 views

optimizing prime number algorithm

I am doing a function to return a list of prime number up to "n", one what to optimize the algorithm is the following: "The next most obvious improvement would probably be limiting the testing ...
1
vote
2answers
3k views

Most efficient algorithm for nth prime, deterministic and probabilistic?

What's the most efficient algorithm for calculating an $nth$ prime, both deterministically and probabilistically? Deterministic Iterate through only odd values, incrementing by $2$. Divide each ...
3
votes
2answers
716 views

Random binary array shows patterns around prime numbers

First post, so please let me know if I'm doing something wrong or if this question does not belong here. I have been toying with java to visualize an interesting 2D binary array I thought of today in ...
2
votes
2answers
288 views

Algorithm to determine if a number is a product of consecutive primes

I want to implement a program in C++ with which I can see if a number $n$ has a prime factorization of only consecutive primes. For example $30=2\cdot 3 \cdot 5$ is such a number, while $21=3 \cdot ...
0
votes
1answer
96 views

Are there any algorithms to check if a big number is a prime number?

I want to check if a given number is a prime number. Are there other ways than brute-force? It should be fast and work with bigger numbers (>1.000.000).
2
votes
2answers
164 views

Special number near $5^{5^3}$

I search the number nearest to $5^{5^3} = 5^{125}$, which is product of two $44$-digit primes. The direct method is : Begin with $N = 5^{125}$. Increase $N$ until the desired number is found. ...
5
votes
1answer
377 views

Random Primes between 4000000000 and 4294967291 (C++)

What is an efficient way to find a random prime between $4000000000$ and $4294967291 $ in C++? This is what I wrote, but it is ridiculous: ...
3
votes
0answers
173 views

Making fermat's little theorem for composite numbers the ultimate test.

It is a programming question but mathematics has a major role to play in it. I have to find the largest prime less than a number $n$. Note that $n\leq10^{18}$. I can go for Fermat's Little Theorem ...
0
votes
1answer
67 views

General term of this sequence

I wanted to know the General term or the function to generate this sequence I found on OEIS. It is the number of ways to express $2n+1$ as $p+2q$; where $p$ and $q$ can be odd prime number and even ...
1
vote
1answer
90 views

Find all expressions of a prime as a sum of four squares

Does anyone know an efficient algorithm to compute all solutions of $$ x^2 + y^2 + z^2 + w^2 = p $$ where $x, y, z, w \in \mathbb{Z}$ and $p \in \mathbb{P}$? By efficient I mean linear on the number ...
5
votes
1answer
151 views

finite field to rational fraction

Suppose I have a number $n\in\mathbb F_p$, i.e. an element of the finite field obtained by arithmetic modulo some (odd) prime $p$. I'm looking for a way to find a simple description of $n$ as a ...
5
votes
2answers
305 views

Proof of Prime Maker Conjecture

In my mind the following conjecture is true: Prime Maker Conjecture I call a number $n$ factor-resistant to $q$ if $q\not\mid n$. Considering $n$ as a composite number, the idea is to make $n$ ...
1
vote
1answer
25 views

If I am checking for $s$ divides $n$ on the interval $S = [3, n-x]$, how large can I make $x$ to ensure I have verified $n$ is prime?

$\forall x \in \mathbb{Z}^+$, $x > 1 \longrightarrow x-2$ does not divide $x$ I have not yet proven this, which might be a good aside for my discrete math. One of my current assignments in ...
0
votes
2answers
172 views

How to prove there is no algorithm for a problem e.g. generating next prime?

Say I want to find the next prime directly without a test. AFAIK there is no known formula. Is it possible that since we've failed to find a formula, then we might be able to prove that there is no ...
4
votes
4answers
553 views

Determining the next Twin Prime?

A really simple I question I guess. Is there an algorithm or method such that given an integer $N$ there is a way to determine the next twin prime pair greater than $N$? If yes, then could you please ...
3
votes
2answers
2k views

How many all prime numbers p with length of bits of p = 1024 bits?

How many all prime numbers p with length of bits of p = 1024 bits? And is there any algorithm which generates all prime numbers p?
2
votes
1answer
219 views

Is the product of 2 unique prime number unique?

I am wondering if I take the product of 2 unique prime numbers, and will the product be unique ? any chance to have collision ? I mean will any other 2 unique prime numbers have the same product ? ...
4
votes
1answer
301 views

Is there a polynomial-time algorithm to find a prime larger than $n$?

Is there a polynomial-time algorithm to find a prime larger than $n$? If Cramér's conjecture is true, we can use AKS to test $n+1$, $n+2$, etc. until the next prime is found, and this method will ...
12
votes
2answers
341 views

Prime one heap Nim

I have been working on an interesting problem my lecturer mentioned recently. Prime Nim is a variant of the Nim game where you have a single pile with an arbitrary number $n\in \Bbb N+\{0\}$ of ...
2
votes
2answers
51 views

Is there any way to split a number with multiplication of some prime number

I am looking for an algorithm which helps me split a number $N$ as such: $$N=p_1^a p_2^b \cdots p_n^z$$ where $N$ is the given number, $p$ is prime numbers smallest to greatest, and $a,b,\cdots,z$ ...
2
votes
3answers
670 views

What prime number generating algorithms are used?

You sometimes hear bout these huge prime numbers (RSA prime number challenge comes to mind) and I was curious about what algorithms or formulas prime-number generators use in practice ? For example in ...
2
votes
2answers
846 views

Expressing a Non Negative Integer as Sums of Two Squares

I'm writing a code in C that returns the number of times a non negative integer can be expressed as sums of perfect squares of two non negative integers. ...
1
vote
2answers
179 views

What is the fastest algorithm to check if a number has only 3 divisors?

Which is the fastest way to check if a number has only 3 unique factors ? Any help will be highly appreciated?
2
votes
0answers
94 views

Searching for prime candidates

For some additional excitement, I've been searching for primes $p \gg q = 104729$, where $q$ is of course the ten-thousandth prime. It seems that the best way to search for prime candidates $p$ is to ...
1
vote
4answers
2k views

Get numbers that have only 2,3 and 5 as prime factors

I am given an integer N. I have to find first N elements that are divisible by 2,3 or 5, but not by any other prime number. ...
3
votes
2answers
1k views

Algorithm to generate a prime number which is n-digits long

Is there an algorithm which, given the number of digits n, generates a prime number which is n-digits long, in polynomial time complexity?
8
votes
1answer
3k views

Pollard-Strassen Algorithm

I'm aware that the Pollard-Strassen algorithm can be used to find all prime factors of $n$ not exceeding $B$ in $O\big(n^{\epsilon} B^{1/2}\big)$ time. This is really useful because I need to find all ...
2
votes
1answer
96 views

Sieve higher powers with logarithmic optimization

I am factoring number $N = 90283$ using quadratic sieve. Bound is $B = 44$. I find factor base to be $\{2, 3, 7, 17, 23, 29, 37, 41\}$. I have $50$ element sieving interval: $\{318, 921, 1526, ...
1
vote
1answer
421 views

Modular Multiplicative Inverse & Modular Exponentiation Equation

I was solving a problem containing that equation. $$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$ Given: $1 \le a \le 2,000,000,000$ $0 \le n \le 2,000,000,000$ $2 \le m \le 2,000,000,000$ $a$ and $m$ ...
2
votes
1answer
2k views

Why choose a prime number as the number of slots for hashing function that uses divison method?

The division method is one way to create hash functions. The functions take the form: h(k) = k mod m Where k is a key and m is the number of slots Edit: If this is my hash function why should ...
13
votes
1answer
1k views

Quadratic sieve algorithm

I am stuck with the sieving stage of Quadratic Sieve algorithm. I've read lots of papers to this point but I can't find any guidlines how to choose sieving interval or how sieving is actually done ...