0
votes
2answers
452 views

On reducible polynomials with positive coefficients, $1$ as constant coefficient and certain bounds on coefficients

Given $a \in \mathbb{Z}$ with $a > 1$. Let $g(x) \in \mathbb{Z}[x]$ be a polynomial with $g(a)=\pm 1$. Let $h(x) \in \mathbb{Z}[x]$ be a polynomial with $h(a)= p$, a prime. Let $g(x)$ and $h(x)$ ...
12
votes
3answers
1k views

Is there a composite number that satisfies these conditions?

We know that if $q=4k+3$ ($q$ is a prime), then $(a+bi)^q=a-bi \pmod q$ for every Gaussian integer $a+bi$. Now consider a composite number $N=4k+3$ that satisfies this condition for the case ...
3
votes
3answers
364 views

Proving a least prime factor

Suppose that I find a small prime factor $p$ dividing a large number $n$ and I wish to prove that it is the least prime dividing $n$. There are two obvious approaches: either factor $n/p$, or divide ...
8
votes
1answer
268 views

Does this notion of pseudoprime relative to a matrix appear in the literature?

Let $M$ be a square matrix with integer entries. Then Fermat's little theorem for matrices holds: $$\text{tr}(M^p) \equiv \text{tr}(M) \bmod p.$$ This follows by an examination of the action of the ...
11
votes
2answers
650 views

Saying things rapidly about integer factorisations

Let $N$ be a positive integer. Thanks to the Miller-Rabin test and the work of Agrawal, Kayal and Saxena, these days people have much much faster algorithms for testing whether $N$ is prime or ...
1
vote
0answers
324 views

Witt rings and prime number generator?

Let $p$ be a fixed prime number. We define the ring of Witt vectors $W(R)$ for any commutative ring $R$ as follows: For every ring morphism $R \rightarrow R'$ the induced morphism $W(R) \rightarrow ...
2
votes
0answers
258 views

Reducing factoring prime products to factoring integer products (in average-case)

My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. (This question has been asked also in the CS ...
2
votes
1answer
1k views

How many cpus needed to check a 100 million digit prime number efficiently? [closed]

If I had access to potentially unlimited CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the mapped ...
1
vote
1answer
316 views

Calculating the constant in the Bateman-Horn-Stemmler conjecture

Bateman & Horn [1], building on Bateman & Stemmler [2], give a conjectured formula for the density of numbers that produce simultaneous primes in a number of fixed polynomials. The constant ...
6
votes
2answers
856 views

Recovering n from sigma(n)/n

For any positive integer $n$, we define $$\sigma(n) := \sum_{d \mid n} d,$$ and $$\delta(n) := \frac{\sigma(n)}{n} = \sum_{d \mid n} \frac{1}{d}.$$ Is there an (efficient) way to determine ...
12
votes
1answer
539 views

Analytic lower bounds on the first sign change of pi(x) - li(x)?

There have been many results on the first sign change of $\pi(x)-{\mathrm{li}}(x)$: among others, Lehman, te Riele, Bays & Hudson, Demichael, Chao & Plymen, and most recently Saouter & ...