# Tagged Questions

An algorithm for determining whether an input number is prime.

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: ...
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!
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
114 views

55 views

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 ...
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.
33 views

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$?
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$ ...
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 ...
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:  \...
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. ...
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 ...
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)...
309 views

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 ...
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 ...
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
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 (...
### 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 ...
### 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)...