Questions tagged [number-theory]

number theory is the branch of mathematics concerning the mathematical properties of numbers and the relationships between various types of numbers. This tag should be used with questions regarding computer science topics which are presented from a number theory perspective or may involve number theory or whose answer could be or should be couched in number theory terms.

47 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
20
votes
0answers
601 views

Complexity of deciding whether there is a winning strategy in the following game

The sum divider game for $n$ starts with the set $M_0 = \{1,\dots,n\}$. Player A chooses a number $m_1$ from $M_0 \setminus \{1\}$ and B has to choose a divider $m_2$ of $m_1$ from $M_1 = M_0 \...
14
votes
0answers
140 views

What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?

In 2014, inspired by Regex Golf, I started exploring, along with a mathematician going by the name teukon, what could be done in the unary domain in ECMAScript regex that went significantly beyond ...
6
votes
0answers
46 views

Level sums, displacements: how to determine their effect efficiently?

Let $R =\mathbb{Z}/N \mathbb{Z}$. Let $f:R\to \mathbb{R}$, $\rho:R\to \lbrack 0,1\rbrack$. We assume that it takes trivial time to compute any given value $f(m)$ or $\rho(m)$. Define $$S(\delta,m) = ...
6
votes
0answers
271 views

Testing algorithm for a modified sieve of Eratosthenes

Context: I am looking at a modified version of the sieve of Eratosthenes. I started by generalising Eratosthenes' sieve, like so: Choose some starting "root", $n_0\in\mathbb{N}$, a sieve limit (the ...
5
votes
0answers
86 views

Given $n=pq=a^2+b^2$, can we factor $n$?

Just to be clear, $a$ and $b$ are known, while $p$ and $q$ are unknown prime numbers, both congruent to $1$ modulo $4$. Can we design an efficient algorithm to retrieve $p$ and $q$? It is a known ...
5
votes
0answers
169 views

Assignment of coprime values to a tree

I recently saw this question somewhere and thought a lot on it but was unable to find an efficient solution for it. Asked on Stack Overflow but got no solution there. The Problem is as follows - ...
5
votes
0answers
541 views

Best complexity of parity/comparison in the Residue Number System

Let: $\left\{m_1, ~...~, m_k\right\}$ be a set of coprime natural numbers, $M=\prod_{i=1}^{k} m_i$ $X$ be a natural integer, such that $X < M$ Then $X$ can be expressed in the Residue Number ...
5
votes
0answers
716 views

Time complexity of finding the largest factor of a number (using a specific oracle)

My question is related to this question posted on math.SE: Given an odd number, what is the quickest (constant-time) algorithm for finding its largest factor and suppose you can call a helper ...
4
votes
0answers
141 views

Optimal parallel-time repeated modular squaring circuit

Given a 4096-bit integer $x$ and a 4096-bit RSA modulus $N$ (of unknown factorisation) what is the fastest circuit to compute $x^{2^T} \mod N$ where $T=2^{40}$. That is, what is the fastest parallel-...
4
votes
0answers
285 views

Reduction from knapsack problem to Integer relation that equals one

My question is related to the Integer Relation Detection Problem which can be formulated as: $\qquad a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0$ Where $\forall i. a_i\in\mathbb{Z} \land a_i<c \land x\...
3
votes
0answers
48 views

Quick calculation for $x^y \bmod 2^d$

I need to calculate $x^y \bmod 2^d$ in $O(d)$ summations/bitwise operations and $1$ multiplication by $y$. $x$ is restricted to be odd, $d\geq 3$. $a$-bit arithmetic (for any $a$) is allowed, as this ...
3
votes
0answers
39 views

How hard is it to find the length of multiplicative 2-partition?

Some terminology at first: Multiplicative 2-partition for number $N$ - a pair of numbers $\{A, B\}$ such that $AB=N$. Minimal multiplicative 2-partition length (denoted $l$) - minimal total number of ...
3
votes
0answers
260 views

Explanation of the extended Euclidean Algorithm

I am looking for some help with understanding the extended Euclidean Algorithm, specifically, this implementation (in Haskell): ...
3
votes
0answers
25 views

Numerical Stability of Halley's Recurrence for Integer $n^{\mathrm{th}}$-Root

tl;dr? See last paragraph. If I use the initial value $2^{\left(\big\lfloor\lfloor\log_2 x \rfloor/n\big\rfloor + 1\right)}$ with Halley's recurrence in the compact form $ x_{k+1} = \frac{x_k\Big[A\...
3
votes
0answers
267 views

How is Chinese Remainder Theorem used in the proof of correctness for RSA

Question At the very end of (most) proofs of RSA's correctness we have something like $$m^{ed}\equiv m\pmod p$$ $$m^{ed}\equiv m\pmod q$$ Therefore by the Chinese Remainder Theorem (CRT) $$m^{ed}\...
3
votes
1answer
1k views

what is the name for the space between the leaves of a tree

I am trying to write a data-type not for a tree, but for the spaces in between the leaves of thee tree. In number theory (a part of math) this is known as a topograph does it have a name in CS?
2
votes
0answers
51 views

Collision between a bi-infinite linear sequence of 2D integer lattice points and any of a fixed set of such sequences

Given: a finite collection $V$ of bi-infinite linear sequences of two-dimensional integer lattice points, each sequence ${V_i}$ given by $\vec{{V_i}_j} = \vec{{V_i}_0} + j*\vec{d_i}$. (A natural way ...
2
votes
0answers
80 views

Counting triplets from three arrays satisfying the equation x^2 = yz

Let's say I have three arrays of positive integers X, Y and Z. You can assume that each of ...
2
votes
0answers
29 views

Is finding a sum of two squares representation for a number computationally assymptotically equivalent to integer factorization?

I have been wondering this question because given a number $n$ with prime factors of the form $4k+3$ when we square $n$ and find a sum of two squares which should reveal these types of factors (as ...
2
votes
1answer
148 views

How to estimate the average time complexity of greatest common divisor?

As we know, the time complexity of $\gcd(x,y)$ is $O(\log \min(x,y))$ by using Euclidean algorithm. Now we fix a constant $n$ and consider the average time complexity of $\gcd(x,n)$. Formally, let $f(...
2
votes
0answers
367 views

Determining whether a number is a perfect square without computing its square root

One of the interesting results of Number Theory is the theory of quadratic reciprocity. One finds that it is possible to determine whether an equation $x^2 \equiv a \pmod p$ has a solution $x$ without ...
2
votes
1answer
137 views

How does RAID-5 algorithm locate the right device?

Please consider the following diagram of a RAID-5 array (Ignore the gray background): Now, given a logical address, how can one return the device number (0-3)? For example, DeviceByLogicalSector(50) ...
1
vote
0answers
30 views

Computability of base-conversion for streams

With regular numbers it is always possible to convert them from one (integer) base to another. But what happens if we consider numbers for which their magnitude is not known in advance, or in other ...
1
vote
0answers
39 views

Is it possible to find length of sum of two binary numbers without calculating sum?

I'm doing an assignment where I need to multiply two 16 bit numbers and store result as an 16 bit integer array. a is binary with length of ...
1
vote
0answers
54 views

Evaluating functions related by Mobius inversion formula

Problem Consider two functions $f: \mathbb{N} \rightarrow \mathbb{N}$ and $g: \mathbb{N} \rightarrow \mathbb{N}$ such that $f(k) = \sum_{d | k} g(d)$ for all $k \in \mathbb{N}$. So, the questions ...
1
vote
0answers
36 views

Decidability of equality of expressions involving exponentiation

Let's have expressions that are finite-sized trees, with elements of $\mathbb N$ as leaf nodes and the operations {$+,\times,-,/$, ^} with their usual semantics as the internal nodes, with the special ...
1
vote
0answers
41 views

Rabin Karp algorithm that uses bitwise AND

I'm reading the source code of JPlag and came across their rabin-karp algorithm implemented found here. Here's the gist of it: ...
1
vote
0answers
96 views

how did the authors of the AKS-Paper come up with the upper bound for r? and what does the multiplicative order have to do with anything?

I have been recently reading the paper "PRIMES is in P", but unfortunately a lot the steps were skipped, which led to confusion. My main problem is with the upper bound on r which was not explained at ...
1
vote
0answers
33 views

Circuit depth of computing the continued fractions of a rational number

If you want to convert a rational number into its continued fraction, what is the circuit depth of this process, in terms of the total number of bits of input? I was reading through some notes which ...
1
vote
0answers
47 views

Branch and scope globally unique identifiers

Say we are working with a Prolog-like system where variables are dynamically created in different branch contexts and scopes, yet these variables are also globally viewable by the system regardless of ...
1
vote
0answers
69 views

System of congruences with non-pairwise coprime moduli

I have a set of congruences x ≡ a1 (mod n) ... x ≡ ak (mod nk) And I want to find x, this can be solved by the Chinese ...
1
vote
0answers
104 views

Algorythm for creating Number-Rows

Given is a list of numbers. Now you build different permutations of that list while there must not be two permutations where the sum of the numbers from any point of the row to the end/beginning is ...
1
vote
0answers
62 views

How does this last step in Shor's algorithm work?

Page 854 of The Nature of Computation states the following (This discussion has made the simplifying assumption that $M/r$ is an integer): If each of the observations gives us a random harmonic, ...
1
vote
0answers
56 views

eVoting with Damgard-Jurik-Cryptosystem

I am trying to implement a secure elecetronic voting system. Therefore I found the Damgard and Jurik Cryptosystem. In their paper the authors describe a secure protocol for "A Length-Flexible ...
1
vote
0answers
34 views

Reducing integer-rooted polynomial to natural-rooted polynomials

First of all, let me define $Dioph(M)$, where $M$ is a set of numbers: $$Dioph({M})=\{p \mid \text{ $p$ is a polynomial with integer coefficients and the zeros of $p$ are in ${M}$}\}.$$ Let $p \in ...
1
vote
0answers
215 views

Finding a sequence of numbers where every product of two mod k is unique

I want to make a sequence of numbers, where I pick the numbers $a_{0}, a_{1},..,a_{n}$. The length of the sequence is $n+1$. Now I want the product of any pair of two numbers in the sequence modulo $...
0
votes
0answers
24 views

Number partition subjected to the cardinality of subset

I hope someone can take some time to consider the following problem and welcome to discuss together. Number partition problem is one of well-known NP-hard problems. Now I am considering the hardness ...
0
votes
0answers
28 views

What is the complexity of (prime?) factorization with a fixed number of primes?

I was wondering what the complexity of factorization (on quantum computers or classical computers) is if we know that there must be exactly two prime numbers and we know the two prime numbers. For ...
0
votes
0answers
23 views

Calculating ring inequalities with fixed precision

Suppose we are given $n$ $M$-bit (the word size of the computer) integers $x_i$, and wish to calculate a linear or nonlinear inequality involving the numbers (an expression made up from the $x_i$, ...
0
votes
0answers
90 views

Fast factorial computation

I'm trying to solve this problem - https://codeforces.com/problemset/problem/711/E I've already found and proved that the result is equal to: $$ 1 - \frac{2^n (2^n - 1) \cdots (2 ^ n - k + 1)}{2^{...
0
votes
0answers
29 views

Radix Economy of Complex Bases

If we extend the allowed bases for a numerical system to the complex numbers, is e still the most economic base? If not, what would it be? There's the well-known formula for radix economy: Where b is ...
0
votes
0answers
55 views

Finding index of $p_{k}$ element in the original sorted array if elements were to be removed using a specific condition

Consider a sorted list of numbers $C_{0}=\{0,1,2,3,...,n-1\}$ from where one element will be eliminated at each step. We are also given a value $L$ in $[0, 1)$ and let the indexing start from $0$. ...
0
votes
0answers
24 views

Need help optimizing an algorithm that's supposed to maximize the greatest common divisor of n elements by removing at most one element

Alright, first here's the text of the problem: You're given n bags of candies where the i-th bag contains a[i] candies and all numbers a[i] are in the segment [1,m]. You can choose a natural ...
0
votes
0answers
24 views

Prove that x and y in extended Euclid's algorithm won't overflow an Integer (If a,b <= 1e8, ax+by=gcd(a,b))

We are given a and b <= 1e8. The extended Euclid's algorithm always finds a solution for ax+by=gcd(a,b) (assuming it exists) which can always be stored in an Int. How to prove the x and y won't ...
0
votes
0answers
61 views

Efficient algorithm to expand $(x+a)^n$

im looking for efficient algorithm to expand $(x+a)^n$ without using binomial theorem is the repeating square method efficient for that problem with the help of binary representation of n ?
-1
votes
1answer
80 views

Number of sequences of given type

Consider that there is sequence $a$ of length $n$ ,$a=[a_i,0\le i\le n]$. Now you are given with $\text{lcm}$ of some pairs of number from list that is, $\operatorname{lcm}(a_i,a_j)=k$ for $0\le i,j\...
-1
votes
1answer
146 views

I want to find the number of steps it takes to find the GCD by Euclidean Algorithm

Let's say I have two numbers a and b. I want to find the number of steps it takes to find the GCD by Euclidean Algorithm by a closed formula which includes parameter a and b. If I go by this ...