Skip to main content

Questions tagged [factoring]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
2 answers
738 views

Is Determining the Number of distinct Prime Factors Polynomial?

Our current understanding of prime factorization states that it is hard to solve. The problem asks us to find the list of prime factors for an integer. For example, 18's prime factors are 3, 3, and 2. ...
abokifas's user avatar
0 votes
0 answers
49 views

Progress towards a Polynomial time factoring algorithm?

This is probably insignificant, but I was messing around with polynomials, and found out that, if we have a number, n = pq that we want to factor, if we expand (k+1)^n -k^n - 1, mod n, the first ...
Colonizor48's user avatar
6 votes
2 answers
3k views

Is there an efficient algorithm to find whether an integer is a prime power?

There's a sentence in the current version of the Wikipedia page for Shor's algorithm which states: we can use efficient classical algorithms to check if $N$ is a prime power. No reference is provided ...
glS's user avatar
  • 286
4 votes
0 answers
52 views

The Hidden Subgroup Problem under different mappings

The Hidden Subgroup Problem (HSP) is an extremely prevalent problem in quantum computation, especially for factorization in Shor’s algorithm. The problem is stated Given an oracle for some function, $...
Wygert G's user avatar
1 vote
1 answer
43 views

Making statements about quantum complexity theory

It is my understanding, based on this question that problems solved on quantum computers with oracles don’t make any statements about BQP in relation to other complexity classes. The fallacy is in ...
Fivefolded's user avatar
0 votes
2 answers
222 views

Finding the time complexity of a prime factorization algorithm

In this question, I'm going to introduce a prime factorization algorithm which I'm working on as my personal project. I may attach a Python code to introduce the algorithm. If it contravenes the rule ...
MYUN's user avatar
  • 11
2 votes
1 answer
136 views

Is GNFS quasi-polynomial-time?

Wikipedia states that the time complexity of the General Number Field Sieve (GNFS) is $$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\log N)^{\frac{1}{3}}(\log \log N)^{\frac{2}{3}}\right),$$ ...
Zirui Wang's user avatar
2 votes
2 answers
398 views

Fast identification of prime power factors?

For a given integer exponent $e$, I want to identify all factors of an integer $n$ which are of the form $p^{e}$, where $p$ is a prime. So, for $e = 1$, this is equivalent to getting the unique prime ...
Logan R. Kearsley's user avatar
0 votes
0 answers
22 views

Link prediction in a network using GNNs versus Matrix Completion and other methods

I am looking at some social network analysis and I need to do link prediction. By link prediction I mean that I only have a subset of the relationships in the network, and I need to make predictions ...
krishnab's user avatar
  • 171
1 vote
1 answer
46 views

Is there a hypothesized "complete" class of problems between P and NP-hard?

For now, assume that P != NP. Is there a "complete" class of problems between P and NP-hard, and if so, what is it called? The two key words here are between complete By between, I mean ...
chausies's user avatar
  • 532
1 vote
1 answer
57 views

Period of modulo exponentiation function from factors

The calculation of the period of the "modulo exponentiation" function: $$ f_a(r) = a^r (mod \ N) $$ is a step of the quantum algorithm for factorizing $N$, where $a$ is a number chosen with ...
Doriano Brogioli's user avatar
0 votes
2 answers
409 views

Integer/prime factorization to 3 SAT

So essentially as the title says, I just want to understand how its done. I have a light idea from my own research, but its failing at one point, and I feel it maybe due to crucial point missing in my ...
khaled sabek's user avatar
0 votes
1 answer
48 views

What is the true space-complexity of saving all divisors, because $N$ can have more divisors than the length of $N$?

$6983776800$ in binary has 33 bits but has $2034$ positive divisors. If a list of divisors were to be logarithmic in N, it needs to take less than 33 bits. I believe there is an infinite amount of ...
The T's user avatar
  • 321
4 votes
1 answer
733 views

What is this algorithm computing and how to prove it?

On Hackerrank I found a test that asks to check what the following algorithm computes: If $x > y$ then $x = x - y$ If $y > x$ then $y = y - x$ If $x \neq y$ then goto 1 Print $x$ Constraints: $...
Kill KRT's user avatar
  • 143
2 votes
1 answer
33 views

How to approximate big composite number factors?

There is a big 1024-bits number A that was obtained by multiplying two numbers B and C.Are there any ways to get first numerical digits of these numbers? How example: ...
Alexandr Dorofeev's user avatar
0 votes
0 answers
46 views

Given $n$ sets of matrices, find $n$ matrices that have the least number of LCDs among their entries

Let's say I have $n$ sets of matrices $$ A = \left\{\begin{pmatrix} 2 & 4 & 17\\ 5 & 6 & 9\\ \end{pmatrix} \begin{pmatrix} 2 & 4 & 18\\ 5 & 6 & 9\\ \end{pmatrix} \right\...
Davide Valdo's user avatar
2 votes
0 answers
76 views

Partition a set of factors so that the difference between products is minimized

I'm sure this problem must be well-known... Given a collection $S$ of numbers, partition them into exactly two sub-collections, $A$ and $B$ (I mean, by definition $B$ is just $S-A$) such that the ...
Quuxplusone's user avatar
0 votes
2 answers
206 views

How would it be possible that primality testing is in P, but not factorization?

Suppose that P != NP. Then there exists 3SAT formulas such that their satisfiability is computationally "evil" (i.e, the satisfiability can be exponentially hard to determine in the size of ...
user avatar
1 vote
0 answers
36 views

If factor isn't found in P-1 algorithm, should upper bound be increased linearly (i.e. +1)

I have seen some implementations of Pollard's P-1 algorithm where the upper bound is only increased by 1 if no factor is found. Such an implementation is described here. Is it sort of missing the ...
northerner's user avatar
5 votes
1 answer
140 views

Factoring algorithms after number field sieves

It seems that the General Number Field Sieve (GNFS) became number one and then RSA stopped its factoring challenges and there have been no advances in factoring algorithms besides quantum computers. ...
Zirui Wang's user avatar
2 votes
2 answers
426 views

How does Pollard's rho algorithm work?

I am trying to understand how does Pollard's rho algorithm actually work, but I just can not wrap my head around it. I already read its section in the CLRS book and ...
razzak's user avatar
  • 172
0 votes
1 answer
56 views

What computational model supports arbitrarily sized integers?

I want to do some research, but I don't think it's important the number of bits it takes to represent the integer input and arithmetic on the abstract machine. So what is the model that addresses ...
HighAsAKiteOnMath's user avatar
2 votes
1 answer
618 views

Prime checking and factorization with just bit cheking

I've read about some methods of prime factorization like here and here. However, I'm wondering: what can we do in prime factorization with just some bit manipulation and without other variables/...
ChocolateOverflow's user avatar
5 votes
0 answers
101 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 ...
Mkch's user avatar
  • 151
0 votes
2 answers
1k views

Runtime complexity of a brute force factoring algorithm? (in terms of bits)

Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the ...
James Fitzpatrick's user avatar
1 vote
1 answer
38 views

Use Fact to decompose a given number

Let Fact be the following decision problem. Given two natural numbers $k \le n$ the machine accepts if and only if $n$ has a non-trivial divisor that is less than or equal to $k$. Prove that if Fact $\...
PCG's user avatar
  • 25
0 votes
0 answers
160 views

Is the Time Complexity of Trial Division Exponential? [duplicate]

I know that there is already a similar question asked on here, but after reading the wiki page on trial division, I am confused, and the other answer doesn't help. The wiki page states that when doing ...
Marcel Mazur's user avatar
2 votes
1 answer
108 views

Time complexity of a problem in probabilistic inference on a Bayesian network

Suppose we have a simple Bayesian network with two rows of nodes: $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$. Each node $x_k$ takes a state of either 0 or 1 with equal probability. Each ...
SapereAude's user avatar
4 votes
1 answer
113 views

Decidability of factoring algebraic equations

Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution: $$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$ And some arbitrary factorization constraints, say:...
JackSprat's user avatar
3 votes
1 answer
654 views

Is integer factorization reducible to subset sum?

Is it possible to solve the FACT (integer factorization) problem in polynomial time if we know the polynomial Subset Sum algorithm? We assume that we know the algorithm solving the problem of Subset ...
Aurelio's user avatar
  • 239
1 vote
2 answers
43 views

Query regarding Integer factorization

Let us consider a product $P$ (whose factors we do not know). Given a base $b$, such that all the Modulus Residues are calculated using powers of $b$ w.r.t. $P$. For some (unknown) power $x$ we know ...
TheoryQuest1's user avatar
1 vote
1 answer
456 views

Congruence of Squares for Factoring [closed]

After coming across the assertion that given $$ x^2 = y^2 \pmod n \\ x \neq \pm y \pmod n $$ we can then conclude that n factors into $$ n = \mathrm{gcd}(n, x-y) \mathrm{gcd}(n, x+y). $...
Apollys supports Monica's user avatar
0 votes
0 answers
67 views

Improving an integer factoring algorithm

I've written an algorithm for integer factorization (specifically RSA-like coprimes - products of two large primes, roughly of the same number of decimal digits) which is not based on QS, GNFS or any ...
plktrautman's user avatar
5 votes
0 answers
331 views

Reduce factoring to solving quadratic equations

The problem of solving quadratic equations is as follows: Suppose you are given a set of quadratic equations and are asked to find $0$-$1$ values for the variables such that all equations are ...
globus1988's user avatar
2 votes
1 answer
226 views

How is integer factoring not in $P$?

Everyone keeps claiming that integer factoring is in $NP$ but I just don't get it... Even with the simplest algorithm (division with all integers up to $\sqrt{n}$) the complexity should be $\sqrt{n}\...
Confused's user avatar
1 vote
1 answer
81 views

Isomorphism of finite dimensional polynomial algebras over finite fields

For a prime power $q$, consider polynomials $f_1,f_2 \in \mathbb{F}_q[x]$. Then, do we have an efficient way of checking whether there exists an algebra isomorphism between: $$\frac{\mathbb{F}_q[x]}{\...
MathManiac's user avatar
1 vote
1 answer
408 views

Proof Review: Integer Factorization is in NP

I want to prove that integer factorization is in NP I have a general idea of how to prove this, and was wondering if I could get a sanity check: I'll show it's in NP by using a non-deterministic TM ...
user69163's user avatar
1 vote
0 answers
236 views

Converting Ambiguous Grammar G to LL(1)

So I am in the process of learning about LL(1) grammar and converting an ambiguous one into LL(1). I know how to figure out if a grammar (G) is ambiguous, however, I am having trouble converting it to ...
ShadowViper's user avatar
1 vote
0 answers
92 views

Is it possible to transform this grammar into LL(1)?

This is the original grammar: S -> ABe A -> ab | a | ϵ B -> b I did try left factoring and this is what I got: ...
Asnira's user avatar
  • 111
3 votes
1 answer
382 views

Complexity class of integer factorization

Is integer factorization confirmed to be an NP-complete problem? If not, then if one could transform IF into an equivalent problem which is already proved to be NP-complete, would it mean that IF is ...
plktrautman's user avatar
0 votes
1 answer
132 views

General number field sieve is slower then exhaustive search for 'small' numbers?

In an attempt to understand the efficiency of the GNFS, I've been looking at runtimes. The calculations seem to indicate the GNFS runs slower than exhaustive search for smallish n. For example: ...
C Shreve's user avatar
  • 471
2 votes
1 answer
53 views

Is the runtime for the general number sieve given in base 10, e or 2?

When the runtime of the GNFS is given as e^(64/9*b(log b)^2)^1/3, what base is the log? I'm assuming its e, but other options would obviously be 10 and 2.
C Shreve's user avatar
  • 471
1 vote
1 answer
159 views

Is the prime factorization problem not an instance of the change making problem?

When using as the set of coins all logarithms of the prime numbers or numbers in general, and when using the logarithm of the number to be factored. The problem is just finding the logarithms that can ...
Askeroni's user avatar
  • 217
3 votes
1 answer
75 views

Is there an alternative to full factorization for testing the Polya conjecture?

The Polya conjecture is a disproved conjecture that states over half the numbers less than any number has an odd number of prime factors. It first fails at $n = 906,150,257$, thus being a good example ...
SE - stop firing the good guys's user avatar
6 votes
3 answers
8k views

Complexity of finding factors of a number

I have come up with two simple methods for finding all the factors of a number $n$. The first is trial division: For every integer up to $\sqrt{n}$, try to divide by $d$, and if the remainder is $0$ ...
qwr's user avatar
  • 618
3 votes
2 answers
172 views

What is fastest algorithm for factoring out square from number

I have $n$-digit integer $N=a^2b$, $b$ is square-free. In other words, $a$ is maximal square which divides $N$. What is fastest known algorithm to find $a$? I can write algorithm of $O(n^2\sqrt{N})$ ...
Somnium's user avatar
  • 275
0 votes
2 answers
215 views

Without primes in $P$ does integer factorization lie in $coNP$?

In integer factorization we ask 'Given $N$ is there a $a\in[2,\sqrt{N}+1]$ such that $a|N$?'. Is the above problem in coNP because we know primes is in $P$? That is there is no such factor $a$ of $...
user avatar
13 votes
2 answers
5k views

Why is FACTOR in Co-NP?

I'm having trouble wrapping my head around the problems PRIME, COMPOSITE, FACTOR and how they're related in terms of complexity. I understand that PRIME has been shown to be in $P$ by the AKS ...
Fequish's user avatar
  • 233
1 vote
1 answer
226 views

What is the most efficient way to find bSmooth values in QS?

The heaviest part of QS is to search for bSmooth numbers. So far I thought about two algorithms for solving this. Trial division calculate $X$ as a product of all the values in the factor base speed ...
Ilya Gazman's user avatar
8 votes
5 answers
4k views

Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently?

First of all, I have just started studying computer science by myself and maybe I just need some clarification of what "polynomial time" means regarding the time complexity of an algorithm and ...
calm-tedesco's user avatar