8
votes
1answer
190 views
+500

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 ...
1
vote
0answers
48 views

Could any one explain the difference between the theorems?

In the paper http://annals.math.princeton.edu/2007/165-2/p04 Theorem 2. Let $b \ge 2$ be an integer. The b-ary expansion of any irrational algebraic number cannot be generated by a finite automaton. ...
4
votes
0answers
91 views

Is it decidable whether the iterates of a polynomial map are bounded?

Let $f:\mathbb{Q}^n\to \mathbb{Q}^n$ be a polynomial map with rational coefficients. Let $p\in \mathbb{Q}^n$. Is there a known algorithm that given this data determines whether or not the iterates ...
1
vote
0answers
50 views

Fast checking Matrix multiplication in mod 10

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In ...
1
vote
4answers
153 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?
0
votes
1answer
50 views

Parity of number of factors up to a bound?

Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$. The question is to find a fast algorithm to find that ...
0
votes
0answers
30 views

Hardness of bounded modular square root of 1

If we know any square root of 1 modulo N different from 1 and N-1, then we can find a nontrivial factor of N. So to find such a square root has a certain hardness. In fact, if in general we ask to ...
1
vote
1answer
35 views

Generalization of Jacobi symbol for higher powers?

Let $n$ be an odd positive integer of unknown factorization, and let $x$ be relatively prime to $n$. The Jacobi symbol $\left(\frac{x}{n}\right)$ gives me partial information on whether $x$ is a ...
0
votes
2answers
52 views

key generation in RSA cryptosystem: why it can be performed in polynomial time?

Suppose that I want to generate the keys of the RSA cryptosystem: the public key will be the couple $(n,e)$ where $n$ is the product of two primes $p$ and $q$ and gcd$(\phi(n),e)=1$.The private key ...
3
votes
2answers
95 views

Big O/little o true/false

These are all from Sipser's book, second edition. I was just hoping someone could verify/explain those that are more difficult for me. $2n = O(n)$: true $n^2 = O(n)$: false $n^2 = O(n\log^2 n)$: I ...
4
votes
1answer
52 views

Complexity of factoring non-squarefree numbers

Consider the two numbers $N_1=p_1\cdot p_2$ and $N_2=p_1^2\cdot p_2$, where $p_1$ and $p_2$ are primes. Is there any factoring algorithm that can factor $N_2$ faster than the asymptotically fastest ...
0
votes
1answer
34 views

Communication complexity example problem

Let $G = (V,E)$ and $H = (W,F)$ be two undirected graphs with $|V| = |W| = n$. G and H are isomorphic if there is a bijection f : V -> W such that: $\{u,v\} \in E$ <=> $\{f(u),f(v)\} \in F$ ...
0
votes
1answer
31 views

Valid proof regarding complexity class?

Consider $L \in BPP \cap NP$. Every string $x \in L$ can be accepted with probability 2/3 since $L \in BPP$. Every string $x \not \in L$ can be rejected with probability 1 since $L \in NP$. This is ...
3
votes
1answer
82 views

Computational Complexity of Finding Adjacent Terms in Farey Sequence

The Farey sequence $\mathcal{F}_n$ is the list of all fractions in increasing order (in lowest terms) from $0$ to $1$, having denominator at most $n$. My question is, given some $a/b\in\mathcal{F}_n$ ...
2
votes
0answers
48 views

Abelian SubGroup Variant:

Consider the following problem: Find integers $x_1, x_2, x_3,\dots, x_n$ Such that: $$P(x_1,x_2,\dots, x_n) = Q$$ for some integer $Q$ and polynomial $P$ where for all permutations of any set of ...
2
votes
1answer
39 views

Differentiating between prime/semi-prime and other integers

Does there exist a test that checks if a number is prime or a semi prime in polynomial time? I am aware that AKS can be used to check primality but what about semi primality? ...
0
votes
0answers
57 views

Quadratic Diophantine Primality Testing

Define a 2-Quadratic Group Operation as the following: A 2nd degree polynomial of the form: $$a_1x_1 + a_2x_2 + a_3x_1^2 + a_4x_2^2 + a_5x_1x_2 $$ Define a primal 2-quadratic group number as an ...
-1
votes
1answer
282 views

Sum of number of divisors of multiples of squares

I wish to evaluate, for some large $N$, $$\sum_{k=1}^N \tau(c\cdot k^2)$$ where $c$ is a positive integer constant, and $\tau(n)$ is the number of positive divisors of $n$ (i.e. $\tau = \sigma_0$). ...
11
votes
1answer
248 views

Why is factorization of large number hard

Why factoring a number is difficult compared to finding out if it is prime (which can be done in polynomial time) ? I would think they might be of similar difficulty in terms of computational ...
2
votes
0answers
100 views

Quadratic Diophantine Equations in Polynomial Time

Considering the problem of finding lattice points $(x_1, x_2 ... x_n)$ that satisfy a quadratic law: $F(x_1, x_2... x_n) = 0$ such that $F(x_1, x_2... x_n)$ is a second degree polynomial It is ...
0
votes
0answers
93 views

How to find the nearest power product?

We call power products the integers of the form $x^m*y^n$ for $m$, $n$, $x$, $y \in \mathbb{N}$. Given a number $u \in \mathbb{N}$, find the closest power product. How does one solve this ...
1
vote
0answers
65 views

Is discrete ultralogarithm harder than discrete logarithm?

Is computing $g^{xy} \bmod{s}$ from $g^{x} \bmod{s}$ and $g^{y} \bmod{s}$ easier harder or the same level of difficulty as computing $g\uparrow\uparrow(xy) \bmod s$ from from $g\uparrow\uparrow x$ ...
3
votes
1answer
60 views

Computing the period of a fraction polynomial in the number of digits

So I have a fraction a/b that is known to be repeating. How do I compute the period of the repeating decimal in polynomial-time in the number of digits of A and B?
1
vote
2answers
68 views

Sequences and Languages

Let $U$ be the following language. A string $s$ is in $U$ if it can be written as: $s = 1^{a_1}01^{a_2}0 ... 1^{a_n}01^b$, where $a_1,..., a_n$ are positive integers such that there is a 0-1 ...
2
votes
1answer
61 views

How big is $Z_n^*$?

I would like to find some upper bound on $\frac{n}{|Z_n^*|}$ i.e. to show that many of the elements in $Z_n$ are also in $Z_n^*$. I want to show that $\frac{n}{|Z_n^*|}=O(log^cn)$ for some $c \in N$. ...
6
votes
0answers
180 views

What's the most efficient algorithm for Divisibility?

What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
3
votes
3answers
138 views

How to find $(-64\mathrm{i}) ^{1/3}$?

How to find $$(-64\mathrm{i})^{\frac{1}{3}}$$ This is a complex variables question. I need help by show step by step. Thanks a lot.
1
vote
2answers
130 views

Möbius function help

Given some large random integer k, how much longer would it take to determine the primality of k, then to calculate mobius(k), and how much longer would it take to factor k, then to calculate ...
4
votes
3answers
97 views

What would be complexity of computing $3^{n^n}$?

Just curious, what would be the computational complexity of computing $3^{n^n}$? I am not sure what it would be like.
2
votes
3answers
348 views

Factoring extremely large integers.

The question is about factoring extremely large integers but you can have a look at this question to see the context if it helps. Please note that I am not very familiar with mathematical notation so ...
1
vote
2answers
297 views

Approximating next prime number

Suppose that there is a prime number. Now I want to approximate the next prime number. (It does not have to be exact.) What would be the time-efficient way to do this? Edit: what happens if we limit ...
2
votes
2answers
138 views

Sum set fixpoint, how many iterations?

I want to approach linear equations of the following form over the integers $\mathbb{Z}$: $$x_1 + \cdots + x_n = 0.$$ I stepped over the sum set, which is defined as follows: $$S + T = \{ x + y ...
7
votes
1answer
666 views

Divisor summatory function for squares

The Divisor summatory function is a function that is a sum over the divisor function. $$D(x)=\sum_{n\le x} d(n) = 2 \sum_{k=1}^u \lfloor\frac{x}{k}\rfloor - u^2, \;\;\text{with}\; u = \lfloor ...
66
votes
4answers
2k views

Complexity class of comparison of power towers

Consider the following decision problem: given two lists of positive integers $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_m$ the task is to decide if $a_1^{a_2^{\cdot^{\cdot^{\cdot^{a_n}}}}} < ...
1
vote
1answer
81 views

Finding a subsequence (of a very long sequence) which does not sum to an even number

[Edited. I've revised to problem to focus on the special case of the integers modulo 2.] You are given a function f from binary strings x ∈ {0,1}n to the integers, or (without loss of ...
4
votes
1answer
172 views

Primality Testing in $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$?

What is known about the computational complexity of primality testing in $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$ where $d$ is a square-free number? For what values of $d$ is primality testing easy ...
6
votes
1answer
279 views

Can a Pratt certificate for a prime be found in polynomial time?

Can a Pratt certificate for a prime be found in polynomial time? I guess this is the same as asking whether the AKS primality test provides extra information that allows $p-1$ to be factored quickly. ...
4
votes
3answers
179 views

Complexity of divisor function

I've been looking at this the past few days, but can't figure it out. Maybe I don have enough mathematical background, but most probably I'm overlooking something super basic from times long gone. ...