0
votes
1answer
324 views

Counterexample to Pólya's conjecture

It is known that Polya's conjecture is false and the smallest counter-example is about $10^9$. Assuming that we are searching for a counter-example not knowing that it exists. What useful information ...
7
votes
1answer
515 views

Can the Legendre symbol be calculated in polynomial time?

Is there an algorithm which on input "$(a,p)$" (where $0\leq a<p$ are integers) takes time polynomial in $\log p$ and outputs "NOT PRIME" if $p$ is not prime and otherwise outputs the Legendre ...
23
votes
1answer
708 views

How strong is this conjecture? $(Z/nZ)^*$ is generated by “small” elements

Conjecture: There are constants $c,k$ such that every $(Z/nZ)^*$ is generated by its elements smaller than $k (\log n)^c$. Where $(Z/nZ)^*$ is the multiplicative group of integers mod $n$. My ...
-6
votes
1answer
143 views

Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that $P-Q \neq 1$ and $N=P^2-Q^2$ [closed]

Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that: $P-Q \neq 1$ and $N=P^2-Q^2$ I am assuming that the best known solution to this problem runs at $O(2^{|N|})$. ...
11
votes
1answer
229 views

Comparing two numbers given their factorization

I'm not an expert, but given the integer factorization of two numbers $a,b$: $$a = p_{i_1}^{a_1}...p_{i_n}^{a_n}, \quad b = p_{j_1}^{b_1}...p_{j_m}^{b_m}$$ What is the time and space compexity of ...
2
votes
1answer
473 views

Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field

I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem: Exponentiating Polynomial Root Problem (EPRP) Let $p(x)$ be a polynomial with $\deg(p) \geq ...
5
votes
1answer
284 views

Subsets of all Diophantine's sets

I have asked this question on math.stackexchange already: http://math.stackexchange.com/questions/627461/subsets-of-all-diophantines-sets Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable ...
2
votes
0answers
110 views

Reference Request: Properties of the Integer Factorization Polytope

The complexity of Integer Factorization is to my knowledge still an open problem, whereas deciding, whether a given integer is a prime number is known to be in $P$ and a proof is available online ...
2
votes
0answers
217 views

cyclotomic polynomials of given degree

Is there a fast algorithm to generate all cyclotomic polynomials $\Phi_n$ for which the degree of $\Phi_n$ is a fixed constant $d?$ This is obviously related to the "inverse totient" function: compute ...
2
votes
0answers
133 views

Odds of projections of a point not on the hyperplane

Let $\mathcal{L}=\{\Bbb x\in\Bbb R^n:x_1+x_2+\dots+x_n=0\}$ be a specific hyperplane. Let a projection of $c\in\Bbb R^n$ be $p(c)=[p_1,p_2,\dots,p_n]$ where $p_i\neq c_i\implies p_i=0$. Let ...
3
votes
2answers
261 views

Efficient representations of natural numbers via arithmetical expressions

A given natural number $n \in \mathbb{N}$ has many representations as expressions mixing other natural numbers and the operators and punctuation symbols $\{+,-,\times,/,\exp,(,)\}$, where '$\exp$' ...
6
votes
4answers
489 views

How long does it take to compute a class number?

I was wondering if there are any known (upper and lower) bounds for the complexity of computing the class-number of a finite extension of the rationals. (A general bound should be in function of the ...
3
votes
2answers
208 views

Complexity of a problem remotely related to the discrete logarithm $A=x g^x$

Let $x,g \in \mathbb{F}_p^\ast$. Given $g$ and either $$ A = x g^ x$$ or $$ A = x g^{x^2-1}$$ find $x$. What is the complexity of solving this? Is there a reduction to the discrete ...
1
vote
1answer
539 views

The smallest altitude amongst the triangles formed by points in the unit circle

Let $S$ be a finite set of points inside the unit circle. Consider all possible triangles formed by three distinct points in $S$, and among all such triangles find the smallest altitude. Denote this ...
13
votes
1answer
423 views

How fast can we numerically calculate Kloosterman sums?

Define the usual Kloosterman sum by $$S(m,n;c) = \sum_{\substack{x \pmod{c} \\ (x,c) = 1}} e\Big(\frac{mx + n\overline{x}}{c}\Big),$$ where $x \overline{x} \equiv 1 \pmod{c}$, and $e(x) = e^{2 \pi i ...
2
votes
1answer
296 views

Problem to a solution

Consider an NP hard problem $\frak P$ which takes an input of length n $\frak P$ can be solved partially by a factor $ p_i = p(n,i)\in$ [0,1)... by a polynomial time algorithm $\mathcal A(i)$ ...
23
votes
1answer
679 views

Are sums of sequences decidable?

Suppose that $f,g$ are rational functions with integer coefficients such that $\sum_{n=0}^{\infty}f(n)$ and $\sum_{n=0}^{\infty}g(n)$ both converge. Is it decidable whether ...
6
votes
2answers
724 views

Approximate number of primes below a given integer?

The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 ...
2
votes
0answers
108 views

supersingular curve detector

Suppose I give you a prime $p$ and ask for a non-CM supersingular elliptic curve over $\mathbb{F}_p.$ Can this be done in polynomial time (so, polynomial in $\log p$)?
2
votes
3answers
275 views

Generating a set of integer passwords that can be securely authenticated

First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it. My question is as follows. Given a positive integer $k$, determine a set of properties ...
17
votes
1answer
2k views

Möbius Randomness of the Rudin-Shapiro Sequence

The Rudin-Shapiro sequence (also known as the Golay-Rudin-Shapiro sequence) is defined as follows. Let $a_n = \sum \epsilon_i\epsilon_{i+1}$ where $\epsilon_1,\epsilon_2,\dots$ are the digits in the ...
3
votes
3answers
714 views

Problem regarding subsets that sum to 0

Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $x_1+\dots+x_n = 0$. Is there a way to find the maximum number of unique subsets any $X$ can have given $n$, such that each subset ...
9
votes
1answer
564 views

Polynomial-time complexity and a question and a remark of Serre

My question is about the theory of complexity, but let me first explain my motivation, which comes from number theory or more precisely from trying to understand a question/conjecture of Serre and a ...
2
votes
2answers
935 views

Number theory and NP-complete

What are some of the natural number theory problems that are np-complete? I am looking for examples not in lattices and geometric number theory. Examples in analytic/algebraic number theory are ok.
7
votes
1answer
616 views

Finding colinear points in F_q^n

Forgive me if this is well known, it's not really my field, but it's a problem I've run across and thought about a bit. Let $\mathbb{F}_q$ be a finite field with $q$ elements, let $n\ge2$, and let ...
2
votes
0answers
271 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 ...
14
votes
3answers
985 views

symmetric integer matrices

Suppose I have a symmetric positive definite matrix $M$ with integer entries. I want to decide whether $M = A A^t,$ with $A$ likewise integral. I assume that decision problem is NP-complete, as is the ...
8
votes
2answers
405 views

Efficient computation of the least fraction with square denominator greater than the square root of 2.

The least rational number greater than $\sqrt{2}$ that can be written as a ratio of integers $x/y$ with $y\le10^{100}$ can be found in a moment using a little Python program. Can anyone write a ...
11
votes
1answer
341 views

The complexity of the leading fractional bit of a power of a rational number

On a mailing list (math-fun) that I subscribe to Dan Asimov asked what's the most efficient way to calculate the leading decimal digits (say 10 of them) of $(p/q)^n \bmod 1$ where $p$ and $q$ are ...
1
vote
1answer
360 views

What are the consequences of a polynomial time algorithm for finding out if a given number is expressible as the sum of two squares?

This question is based on this question, in which it is asked if there is a polynomial time algorithm which finds out if a given number is expressible as the sum of two squares. One of the answers ...
11
votes
1answer
1k views

Computing exponential sums rapidly?

I am looking at sums of the form $\sum_{N\le n \leq N+M} e(P(n))$ where $P\in R[x]$ is a polynomial of bounded degree. Let's say $M\sim c N$ (and $N$ is large). The question is - when can one ...
32
votes
3answers
3k views

Testing whether an integer is the sum of two squares

Is there a fast (probabilistic or deterministic) algorithm for determining whether an integer n is a sum of two squares? By "fast" here I mean polynomial time (i.e. time O((log n)^{O(1)})). Note that ...
38
votes
2answers
5k views

Walsh Fourier Transform of the Möbius function

This question is related to this previous question where I asked about ordinary Fourier coefficients. Special case: is Möbius nearly Orthogonal to Morse ! Harold Calvin Marston Morse (24 March ...
21
votes
3answers
2k views

Discrete Fourier Transform of the Möbius Function

Consider the Möbius function $\mu (m)$. (Thus $\mu(m)=0$ unless all prime factors of $m$ appear once and $\mu (m)=(-1)^r$ if $m$ has $r$ distinct prime factors.) Next consider for some natural number ...
1
vote
1answer
3k views

Finding the square root modulo n, when the factors of n are known

Last month, I asked whether there is an efficient algorithm for finding the square root modulo a prime power here: Is there an efficient algorithm for finding a square root modulo a prime power? Now, ...
3
votes
3answers
720 views

A conjecture on a Subset Power Sum Problem motivated by Computer Science

Let $X=\{x_{1}, \cdots , x_{n}\}$ be a set of $n$ positive integers and integer $i \ge 1$. Let’s say that the set $X$ is $i$-sum-avoiding if for any nonnegative integers $c_{1}, \cdots, c_{n}$ such ...
10
votes
3answers
585 views

Efficiently getting bits of N! ?

Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$? ...
11
votes
0answers
565 views

Regular languages of matrices and their generating functions

My question is somewhat related to this question. Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...
6
votes
2answers
1k views

Can a number be factored quickly, given the sum of its prime factors?

This is perhaps most naturally phrased as a promise problem. Given numbers $n$ and $s$, where $s$ is the sum of the prime factors of $n$ (distinct or with multiplicity; I imagine both variants will ...
5
votes
1answer
262 views

Speeding the quadratic sieve with an oracle

Suppose we have an odd composite $N$ and want to find numbers $a_1,\ldots,a_k$ such that each $a_i^2$, reduced mod $N$, is $b$-smooth. Of course we can use the quadratic sieve algorithm (minus the ...
11
votes
2answers
719 views

Which recursively-defined predicates can be expressed in Presburger Arithmetic?

In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...
8
votes
3answers
822 views

Boolean Cube of Primes

For a large enough $n$, and a parameter $ m $ I'm looking for a subset of the prime numbers in the range $[n,2n]$ with a unique structure. I am looking for a prime $p$ and a set of $m$ positive (not ...
12
votes
3answers
2k views

Zero-knowledge proof of positivity

If I have committed to a number x by revealing g^x mod p, can I prove that 0 < x mod (p-1) < (p-1)/2, i.e. that x is positive, without leaking any more information about x? My bounty is ending ...
6
votes
2answers
539 views

Funky congruences

Suppose we have the remainders: {$(a^0_1, a^1_1), \ldots, (a^0_n, a^1_n)$} and the moduli {$c_1, \ldots, c_n$}. We want to know if there exists $b_1, \ldots, b_n \in$ {0,1} and $m \in \mathbb{N}$ such ...
0
votes
2answers
1k views

Time complexity of finding the GCD of a set S as a function of sum(S)

The algorithm to be used is: Sort the set into ascending order $x_1 = s_1$ $x_i = gcd(x_{i-1},s_i)$ $GCD = x_n$ What I'm looking for is expected run time as a function of $\sum_{i\in S}i$ As a ...
5
votes
4answers
671 views

Reconstructing a fraction from its first digits

It is not difficult to see that any reduced fraction $\frac{p}{q}$ where $0 < p < q $ and both $p$ and $q$ have at most $N$ digits (where $N$ is a fixed integer) can be reconstructed from its ...
12
votes
4answers
1k views

Complexity of testing integer square-freeness

How fast can an algorithm tell if an integer is square-free? I am interested in both deterministic and randomized algorithms. I also care about both unconditional results and ones conditional on GRH ...
18
votes
4answers
2k views

Discrete logs vs. factoring

One thing that I've never quite understood is why computing discrete logarithms (in the multiplicative group mod p) and factoring seem to be so closely related. I don't think that there's a reduction ...