An algorithm for determining whether an input number is prime.

learn more… | top users | synonyms

0
votes
0answers
18 views

New Generalized MR-test

I am conducting a new Miller Rabin (SPRP test) and editing the first step. Can someone please help me with the last step. Thanks. Original: Write $n$ $=$ $2^sd+1$ with $d$ odd. Replace: New Test: ...
2
votes
2answers
69 views

Can this function be a new test for primality?

The following function returns always 0 only if a number is not prime. $$ H(x)=\prod_{i=2}^{x-1}\left\{\left[\sum_{k=1}^{x/i}(-i)\right]+x\right\} $$ what do you think? Bye!
2
votes
3answers
66 views

$p\in\mathbb P\iff\Big(2\leq k<\sqrt p\implies\gcd(k^2,p-k^2)=1\Big ),\;p>3$

This is sharper variant of A condition for being a prime: $\;\forall m,n\in\mathbb Z^+\!:\,p=m+n\implies \gcd(m,n)=1$ It seems enough to test that for some sums: $p=m+n\implies\gcd(m,n)=1$, namely ...
3
votes
1answer
167 views

Generalization of Inkeri's primality test

How to prove that following hypothesis is true ? Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are ...
0
votes
0answers
70 views

Primality test for $F_n(10)=10^{2^n}+1$

Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers . Theorem Let $F_n(2)=2^{2^n}+1$ ...
1
vote
1answer
42 views

User directed prime testing for smallish integers (100-1000 decimal digits)

I have become interested recently in (A1) what one can do, if anything, about ~100 digit numbers with no easy factors and no access to anything but basic calculators/software that can cope with ...
2
votes
0answers
19 views

Exploring congruences and identities involving Mersenne primes and the terms of Lucas-Lehmer test

When I was exploring congruences$\dagger$ involving the terms $S_k$ defined in Lucas-Lehmer test (this reference is the Wikipedia, but the main reference is Crandall and Pomerance, Prime Numbers: A ...
1
vote
2answers
55 views

The eventual advantage of a primality test without known exceptions

The primality test of Fermat with base $2$ seems to be as secure as the computer hardware for testing numbers big enough. However, I think there are an infinite numbers of false primes using this ...
4
votes
1answer
133 views

Is the Fermat primality test secure enough for very big numbers?

The random variable $X_m$ is the number of trials before $n\notin\mathbb P\wedge n|2^{n-1}-1$ where $n$ is an odd random integer $2^{m-1} < n < 2^m$. Computer simulations makes me believe ...
1
vote
1answer
53 views

Primes is in P, proof of hendrik Lenstra Jr. lemma

In the paper describing AKS primality test : http://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf On page no. 8 Lemma 4.7 last paragraph, I cannot understand how number of ...
2
votes
1answer
114 views

“Practical” Sieve of Eratosthenes from “Primes Numbers - A Computational Perspective”

Consider the following pseudocode for the Sieve of Eratosthenes, giving us the primes up to $N$: 1) List the numbers $2$ to $N$. 2) Let $p=2$. 2) Cross out $p^2$, then cross out $(p+1)p, (p+2)p, (...
4
votes
0answers
55 views

Why using primes as base in the Rabin-Miller test?

I have done some computer tests with the Rabin-Miller primality test: To test an odd number $n$, write $n=2^r\cdot s + 1$, where $s$ is odd. Given a number $a$ such that $1<a<n-1$, if $...
0
votes
0answers
55 views

Primality test for Thabit numbers of the first kind

Definition 1 Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers . Definition 2 Let $T_n=3 \cdot 2^n-...
7
votes
1answer
155 views

Why can this cosine sum function show all primes less than $N^2$?

I constructed this cosine sum that puts all primes within N on line y=1, and its zeros show the sieve by primes less than N. For $x<N^2$, they are all primes. $$ P(N,x)=\sum_{n=2}^{N}\frac{1}{n}\...
5
votes
1answer
252 views

Conjectured primality test for $F_n(28)=28^{2^n}+1$

How to prove that following conjecture is true ? Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are ...
4
votes
1answer
133 views

Can we replace the upper limit condition of the Sieve of Eratosthenes $\sqrt{n}$ with the value $\sqrt{p}$ where $p$ is the last sieved prime $\lt n$?

By chance I stumbled upon the OEIS list A033677 of the smallest divisor of $n$ greater or equal to $\sqrt{n}$. Roughly speaking if we use the classic enhanced sieve of Eratosthenes, $\sqrt{n}$ is the ...
0
votes
1answer
120 views

Pseudo-primality test for Mersenne numbers faster than Lucas-Lehmer test?

Definition Let $M_p=2^p-1$ with $p$ prime and $p>2$ . Lucas-Lehmer Test $M_p$ is prime if and only if $S_{p-2} \equiv 0 \pmod {M_p}$ where $S_{k+1}=S^2_{k}-2$ and $S_0=4$ . Pseudo-Primality ...
-1
votes
1answer
44 views

Cryptography using groups [closed]

For my math essay I decided to explore the use of group theory in cryptography; as opposed to looking at the coding algorithms I'd like to look more at the math behind it, assuming I know the basis of ...
9
votes
0answers
199 views

If $b$ is even and not a power of two, can $b^4+1$ be a weak pseudoprime?

The complete question is already in the title but we shall provide some motivation as well. We study generalized Fermat numbers defined by: $$\mathrm{GF}(n,b) = b^{2^n}+1$$ where $b$ and $n$ are ...
0
votes
1answer
56 views

Prove that Absolute Pseudoprimes or Carmichael numbers are square free.

The proof given in David Burton is as follows Suppose that $a^n\equiv a$ mod($n$), for every integer $a$, but $k^2\,|\,n$ for some integer $k>1$. If we let $a=k$ then $k^n\equiv k$ mod($n$). ...
0
votes
1answer
32 views

Has the Pascal-like triangle of semiprimes a hidden primality test or there is a counterexample?

This is an observation regarding the semiprimes, also named 2-almost primes, biprimes, or the product of two primes. Basically it seems that if the semiprimes are arranged in a Pascal-like ...
3
votes
2answers
69 views

What happens in elliptic curve primality testing if you cannot find a suitable discriminant?

I'm trying to understand the computational aspect of elliptic curve primality testing (specifically the Atkin-Morain test), and in general, I understand why it works for a prime number. However, when ...
0
votes
1answer
58 views

$2^k+3$ : Primality Brute Forcing Theory Below The Square Root

I'm testing a theory of brute forcing $2^k+3$. I've tried to test $(2^k)+3$ where $k=84$ but my computer just takes too long... Java takes too long too.. It's pretty stupid to assume 83 tests makes ...
4
votes
1answer
121 views

Some heuristics about the Pisano Period, primes and Fibonacci primes. What reasons are behind them?

I started to read about the Pisano Period, $\pi(n)$, applied to the classic Fibonacci sequence and made some simple tests looking for possible properties of the sequence. I have observed the following ...
1
vote
2answers
57 views

Prove that $τ(m^n)$ and $n$ are coprime $(m,n ∈ N^+)$

We have that $τ(n)=\sum_{d|n} 1$ is the number of dividers of n. Dividers of $m^n$ are $1,m,m^2,...,m^n$ then we have that $τ(m^n)=n+1$. Is this correct so far? Now we must prove that $τ(m^n)$ and $...
2
votes
1answer
47 views

How many times do I loop Solovay--Strassen primality test

First, I am aware of this former thread: math.stackexchange Yet it doesn't answer my question. If I want to check if an integer $n$ is prime using the Solovay--Strassen test, how many times do I ...
2
votes
1answer
110 views

Leibniz theorem : A natural number $p> 2$ is prime iff $(p - 2)!-1 \equiv 0 \pmod p$.

I thought of using Wilson's theorem for the proof. First we have by Wilson's theorem $$(p - 1)!+1 \equiv 0 \pmod p$$ We can write this as $$(p - 2)!(p-1)+1 \equiv 0 \pmod p$$ $$(p - 2)!(p-1)+1=p(p-...
0
votes
0answers
21 views

If, for some odd integer $n$, $P_n$ is the set of all bases $b$ in which $n$ passes a Fermat test, find the order of $P_n$.

I'm in a fourth year number theory course. The final exam is in two days and I can't figure out where to start with this question. It says to prove that $\operatorname{ord}(P_n) := \prod_{p\mid n} \...
2
votes
1answer
61 views

Why it is so difficult to perform primality test on huge fermat numbers?

I am not good in computer programming at all, but I know that it will take a lot of times to perform primality test on huge numbers (10 million or billion of digits). But I particularly get interested ...
2
votes
2answers
89 views

Miller-Rabin primality test for $2^{32}+1$

How can I prove that $2^{32}+1$ is composite number using Miller-Rabin primality test? I can't find a solution which verify the hypothesis of theorem.
2
votes
0answers
33 views

Conditions that suffice to show compositeness using Miller-Rabin test

I'm trying to sort out two descriptions of the Miller-Rabin test for primality: the one from Rabin's original paper and that from Wikipedia's article. Let $n$ be the number we wish to test, and let $...
0
votes
1answer
23 views

Probability of an aleatory experiment conducted $n$ times

What is the probability of an aleatory experiment conducted $n$ times? For example, say we choose randomly a number $x$ from a known interval, which happens to contain some certain kind of numbers we'...
1
vote
1answer
58 views

Could Miller-Rabin primality test give false negative?

Could Miller-Rabin primality test give false negative, for example when test prime number and gives it as composite? I know that it could give false positive (giving composite number as prime), but ...
4
votes
1answer
72 views

Why is $\gcd(2^p + 1,3^p + 1) = 1$?

Let $p$ be an odd prime. Why is $\gcd(2^p + 1,3^p + 1) = 1$ ? I tried using fermat's little and $\gcd(a+b,a) = gcd(a,b)$ but without succes. I can make a statistical argument that suggests there are ...
0
votes
1answer
58 views

Generating false positives to the Rabin-Miller primality test

For what composite numbers $x$ will $a^{x-1} \equiv 1 \pmod x$ for $a \in [2,n]$? Can we generate $x$s that give false positives to the Rabin-Miller test for the first, say 10, consecutive integers $...
1
vote
0answers
37 views

Prove that a set of numbers can never consist of prime numbers

I noticed that for any integer $n>0$, $14^n+11$ would not be prime for up to $n=4$. Does this hold for all $n$? Is there a way to prove this or is this something that only works for some $n$?
5
votes
1answer
77 views

pseudo-primality and test of Solovay-Strassen

Let $n$ be an odd integer, we say that $n$ is $a$-pseudoprime if $gcd(a,n)=1$ and : $$\begin{pmatrix}\frac{a}{n}\end{pmatrix}=a^{\frac{n-1}{2}}\text{ mod } n $$ Euler's criterion states that if $n$ ...
3
votes
2answers
115 views

Understanding Carmichael Number

A Carmichael number is a composite number $n$ which satisfies the modular arithmetic congruence relation $$a^{n-1} \equiv 1 \pmod n$$ $\forall a \in \mathbb Z_n$ such that $\gcd(a, n) = 1$ Wiki says ...
5
votes
2answers
72 views

Checking primality for $2 \uparrow \uparrow n + 3 \uparrow \uparrow n$

Is there a clever way to test primality for $$2 \uparrow \uparrow n \quad + \quad 3 \uparrow \uparrow n$$ where $n \gt 3$? (Not surprisingly, I got stuck after that) For $n \le 3$ we get: $$ \...
2
votes
2answers
82 views

Why does Miller-Rabin algorithm check for perfect powers?

I was reading the following version of the Miller-Rabin algorithm: it can also be found on page 6 of the following notes. The first if statement checks wether the input $n$ is a perfect power. i.e. ...
5
votes
1answer
42 views

Existence of a prime in between two integers, of which the larger integer is divisible by all prime divisors of the smaller integer.

Let $a$, $b \in \mathbb{N}$ and $3 < a < b$. Suppose all prime divisors of $a$ divide $b$ and all prime divisors of $b$ less than $a$ also divide $a$. Does there always exist a prime $p$ such ...
0
votes
0answers
67 views

A program for Primality Test for very large numbers

I need to test if a number is a prime number. Is there any program to test very large numbers like the biggest one with 17,425,170 digits ? I know about the Great Internet Mersenne Prime Search (GIMPS)...
3
votes
1answer
309 views

Conjectured primality test for specific class of $N=k\cdot 6^n-1$

How to prove that this conjecture is true ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ x ...
1
vote
3answers
106 views

Fermat primality test $\gcd$ condition and carmichael numbers

Consider the following quote (I read similar thing in a couple of sources but this one illustrates the issue I'm having): By Fermat's Theorem if $n$ is prime, then for any $a$ we have $a^{n-1} = 1 ...
1
vote
2answers
163 views

Primality of $2^{255}-19$

I need a test for primality that I apply to $2^{255}-19$ (which is claimed to be prime) and certify to be correct with the ACL2 theorem prover. This means that I must be able to code the test in ...
0
votes
0answers
274 views

$S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$, $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ iwth composite and prime numbers

I have two sets with $n>2$ natural number: $S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$ $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ Can anyone explain me if there are prime ...
-3
votes
1answer
71 views

Rabin-Miller compositeness

Find a witness Rabin-Miller of compositeness of $n=25$ Can anyone explain and show me a way on how to solve this question?and generally how to find witness Rabin-Miller
5
votes
0answers
185 views

Is there a quicker way to generate integers which are hard to factor than multiplying two large primes?

An easy way to generate an integer which is hard to factor is to find two large primes and multiply them. As a bonus, you know the factors. I'm interested in whether it's possible to find integers (...
0
votes
1answer
47 views

Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n

Given the number $n=35$.Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n I found this problem on internet and i am trying to find a solution ...
4
votes
1answer
74 views

Why are there not primality tests based on comparing the candidate $n$ with values of some $k \in [0,n]?$

I am learning basic number theory and as far as I could read, basically all the primality tests (or proven primality theorems) that are able to decide if a given $n$ is prime (or a special pseudoprime)...