The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
41 views

Devising an Algorithm for Linear Combination with Column Restrictions

Application: We intend to factor an integer $N$ using a variation of the rational sieve. This involves constructing a congruence of squares modulo $N$ from a set of linear relations $$x - N = y$$ ...
-1
votes
1answer
21 views

How n (1+b) is not prime? [closed]

Here is the complete proof taken from this link How do I convince myself that n(1+b) is not prime when b>=1? Here is what I did: if n is 3 and b is 3. Then ...
3
votes
0answers
29 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) ...
1
vote
1answer
43 views

Quadratic Diophantine equation - Polynomial Time Cases

In number theory, solving a Quadratic Diophantine equation (a, b, c constants) $$ a*x^2+b*y= c $$ is an NP-Complete problem. Even for a=1, the problem remains NP-Complete. The solution (x, y) are ...
2
votes
1answer
35 views

Efficient computation of traces of all primitive elements in field extensions of GF(2)

Let $n > 1$ and let $\mathbb{F}_{2^n}$ be the finite field with $2^n$ elements. The trace function $T(x) = x + x^2 + x^{2^2} + \cdots + x^{2^{n-1}}$ is an onto linear transformation from ...
1
vote
0answers
21 views

Finding all “smooth” numbers up to 10^6 — problem with nested loops [duplicate]

A [smooth number] is one whose factors are all "small". For a computational problem, I would like all smooth numbers up to $10^8$. I think it's unfeasible to factor a billion numbers. Instead, I ...
4
votes
2answers
166 views

How can I generate first n elements of the sequence 3^i * 5^j * 7^k?

How can I efficiently generate the first N elements of the sequence $3^i 5^j 7^k$, where $i,j,k \in \mathbb{N}$? I've googled around a bit and found the sequence in OEIS, but I don't really see a ...
0
votes
2answers
53 views

Introduction to number theory [closed]

What is the best book for a beginner in Introduction to number theory? I am new to this field and getting deeper into cryptography, so I think reading some intro books about number theory can be of ...
-1
votes
2answers
82 views

What is complexity of checking whether a natural number is a perfect square? [closed]

As the title says, what is complexity of checking whether a natural number is a perfect square?
1
vote
1answer
42 views

Smallest possible integer not obtained from sumset

Given a number N, and some set $A=\{a, 1\le a\le N\}$, and let $B=\{\text{every integer} \in [1,N]\}$, and $C=B\setminus A$ (Set C has all values from B not in A) What is the best way of finding the ...
5
votes
1answer
39 views

Fast polynomial calculation over $\mathbb{Z}_{487}$

Given a polynomial $a(x)$ of degree at most $242$ over $\mathbb{Z}_{487}$, I'd like to choose distinct values $x_0, x_1, . . . , x_{242} ∈ \mathbb{Z}_{487}$, such that I'll be able to calculate $a(x_j ...
2
votes
2answers
42 views

Finding the values of x and y using base 8 [closed]

In finding the values of x and y, if (x567) + (2yx5) = (71yx) ( all in base 8) I proceeded as under. I assumed x=abc and ...
3
votes
1answer
53 views

Listing integers as the sum of three squares $m = x^2 + y^2 + z^2$

I would like to write an algorithm that lists all the ways a natural number $m \in \mathbb{N}$ can be written as the sum of three squares $m = x^2 + y^2 + z^2$ with integers $x,y,z \in \mathbb{Z}$. ...
4
votes
1answer
626 views

What does the set {n | n is an integer and n = n + 1} represent?

I am reading Michael Sipser's book Introduction to the Theory of Computation, which mentions the set $$S = \{ n \mid \text{$n$ is an integer and $n = n + 1$}\}.$$ This doesn't make any sense to me. I ...
5
votes
1answer
48 views

Runtime of Euclidean Algorithm

Given two $n$-bits numbers $a$ and $b$, I am not sure on how to find the runtime of the euclidean algorithm for finding the $\gcd$ of $a,b$. The problem (for me) in here is that apart from the size of ...
1
vote
1answer
25 views

A problem regarding Extended Euclidean Algorithm

Alex has some (say, n) marbles (small glass balls) and he has going to buy some boxes to store them. The boxes are of two types: Type 1: each box costs c1 Taka and can hold exactly n1 marbles Type ...
4
votes
1answer
62 views

Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form

As stated in the title: Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form. For example: when $p = 2$ and $q = 3$ Next of $2^2*3=12$ is ...
1
vote
2answers
107 views

Proving that $2^n$ does not divide $n!$ [closed]

How can prove that $2^n \nmid n!$ using binary representation for $n!$ and $2^n$.
0
votes
2answers
41 views

Algorithm for generation of Canonical represented integers [closed]

Is there a way to get canonical representation of an integer by algorithm? I can get primes, but I don't know how to represent, for example, 1000 as 2^3×5^3. How ...
5
votes
1answer
102 views

Complexity of Pythagorean triples

We define a Pythagorean triple as a triple $\langle a,b,c\rangle$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$. In order to avoid duplicates, we say that a triple $\langle a,b,c\rangle$ is legit ...
1
vote
1answer
40 views

Number of nonnegative solutions of linear Diophantine inequality

Given inequality $Ax + By \le C$, where $A, B, C$ are integers, $A$ and $B$ are coprime and $C < AB$. I need to find number of non-negative integer solutions of it. Is there exists algorithm which ...
1
vote
1answer
78 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 ...
4
votes
3answers
144 views

counting arithmetic progressions $a, a+r, a+2r$ in a list

I have a large list $L$ of numbers and I need to count instances of elements $a,b,c \in L$ such that $a +c = 2b$. A brute-force approach would be to check all possible triples $(a,b,c)$ and this will ...
4
votes
1answer
133 views

Efficiently finding the maximum pairwise GCD of a set of natural numbers

Consider the following problem: Let $S = \{ s_1, s_2, ... s_n \} $ be a finite subset of the natural numbers. Let $G = \{$ $gcd(s_i, s_j)$ | $s_i, s_j \in S,$ $ s_i \neq s_j \}$ where $gcd(x,y)$ is ...
2
votes
1answer
53 views

Checking whether a number is a square or higher power modulo n

Is there an algorithm to check whether an integer $x$ is a square modulo $n$, where $n$ is an integer whose factorization we do not know? Is the Jacobi symbol helpful? What about higher powers, ...
2
votes
2answers
179 views

Breaking up sum of power of 2s

I'm writing an algorithm to solve a research problem involving searching for numbers on very large arrays. I encountered a sub-problem that requires me to break up sums of numbers which are power of ...
1
vote
1answer
46 views

Reversing Key Algorithm

I have to craft up a number made of 19 digits so that, after some mathematical operations made 11 times, the resulting sum of the remainders of the first ten operations is equal to the the remainder ...
5
votes
2answers
71 views

Quick calculation for $(x^y) \bmod z$

What are the possible ways to calculate $(x^y) \bmod z$ quickly for very large integers? Integers $x,y \lt 10^{10000}$ and $z \lt 10^6$.
1
vote
1answer
131 views

Why don't people use Fermat's little theorem to check if number is prime?

There're a lot of examples of code for checking if a number is prime. Why don't people use Fermat's little theorem, i.e. this simple formula $\qquad a^{p-1} \equiv 1 \pmod p$, to check if a number ...
1
vote
1answer
95 views

Number of K-sets [closed]

I am having a plane in N dimension. Th distance between 2 points (a1,a2,...,aN) and (b1,b2,...,bN) is max{|a1-b1|, |a2-b2|, ..., |aN-bN|}. I need to to know how many K-sets exist(here K-set refers to ...
3
votes
2answers
134 views

Implement Mathematica's capability of rationalizing machine reals

If I have a variable x bound to a machine precision real in Mathematica, I can use y = FromDigits[RealDigits[x]] then y is ...
2
votes
1answer
98 views

Are there pseudorandom number generators (PRNG) with no finite period?

The typical and widely used PRNG, the linear congruential generator always has a finite (though possibly "long") period. Are there PRNGs that have no finite period? For this question it is not ...
0
votes
1answer
44 views

What is growth of $\psi_q(m) = \min \{ p: m ∣ (q^p−1) \}$ for fixed $q$?

I have to estimate the computational complexity of some algorithm that does $\psi_q(m)$ iterations. Assume that all inputs $m$ are coprime to $q$. So I need to know what growth the $\psi(m)$ has.
3
votes
1answer
56 views

2SUM with a weight

Suppose we have a $n\times n$ symmetric matrix $\mathbf A$. I want to know if there exists two elements of a vector $\mathbf x$, let's call them $x_i,x_j,i\ne j$, such that $x_i +x_j+[A]_{i,j}\ge y$ ...
3
votes
1answer
464 views

Shift-and-or multiplication operation

Continuing in the same vein as Carry-free multiplication operation, a followup question is as follows (differences in bold): Let $r = p \oplus q$ be an operation similar to multiplication, but ...
3
votes
2answers
246 views

Carry-free multiplication operation

In long-multiplication, you shift and add, once for each $1$ bit in the lower number. Let $r = p \otimes q$ be an operation similar to multiplication, but slightly simpler: when expressed via ...
4
votes
0answers
270 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 ...
2
votes
1answer
64 views

Finding number of numbers dividing n^m exactly p times

Suppose I am given a number $n$ (less than $10^8$) and $m$ (less than $10^7$) and $p$ (less than $10^4$), I have to write a program to find number of numbers that divide $n^m$ exactly $p$ times. ...
3
votes
1answer
186 views

integer factoring using Fermat's method

Reading an article on integer factorization I implemented the following - rather inefficient - factorization method: Every odd composite can be factored as a difference of squares: $$ ab = ...
5
votes
1answer
157 views

How hard is factoring a complex number?

Given complex number $C=a+ib$, I want to find two complex numbers $C_1=x+iy$ and $C_2=z+iw$ such that $C=C_1*C_2$ (a,b,x,y, z and w are all non zero integers). This problem is at least as hard as ...
4
votes
0answers
277 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 ...
1
vote
1answer
528 views

Recursive definition of sum of two numbers in terms of the successor function

This is a question from the book Data structures using C and C++ by Tenenbaum. Not a homework problem but self-study. Recursive definition of a+b, where a and b ...
3
votes
2answers
72 views

Remove divisors from a set of integers

I have a set $S$ of integers. I want to remove all elements of $S$ that are divisors of another element of $S$. In other words, I want to compute $T = \{y \in S : \forall d \in S . d \nmid y \}$. ...
3
votes
2answers
775 views

Find out the largest LCM of the partitions of n

I want to find out an algorithm to find out the largest least common multiple (LCM) of the partitions of an integer $n$. Example: $5 = 1 + 4$, $5 = 2 + 3$, since $\mathrm{LCM}(1,4) < ...
12
votes
1answer
381 views

Complexity of taking mod

This seems like a question that should have an easy answer, but I don't have a definitive one: If I have two $n$ bit numbers $a, p$, what is the complexity of computing $a\bmod p$ ? Merely ...
6
votes
0answers
177 views

The length of the smallest co-prime chain between any two integers

I found a variant of this problem in one of the recent algorithms competitions. Given any two integers ($A,B, A \lt B$), find the least number, $L$, of integers between $A$ and $B$ ($N_i, 1 \lt i ...
2
votes
1answer
50 views

Faster Algorithm for Computing Norm

Can anyone suggest an algorithm faster than $\Theta(n^{2})$ for computing the following function: $$||n||:=\frac{1}{\max\{k \in \mathbb{N}: 1|n, 2|n,\ldots,k|n\}}$$
10
votes
2answers
985 views

Finding the size of the smallest subset with GCD = 1

This is a problem from the practice session of the Polish Collegiate Programming Contest 2012. Although I could find the solutions for the main contest, I can't seem to find the solution for this ...
11
votes
0answers
281 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 ...
6
votes
1answer
267 views

Quadratic residue and integer factoring

I often read that deciding whether or not a number $r$ is a quadratic residue modulo $n$ is an interesting (and hard) problem from number theory (especially if $n$ is not prime). I am looking at the ...