For questions about finding factors of e.g. integers or polynomials

learn more… | top users | synonyms

0
votes
0answers
56 views

Figuring $x$ where $x = \max \{ \operatorname{round}(7),0 \}$

I'm a software developer and do very little with math but I have been called upon to incorporate a math function into my app I'm developing. I'm stumped as to how to figure $x$ where $x = \max \{ ...
2
votes
2answers
519 views

Number of factors less than a number

I need to find the number of factors of a large number $n^2$ that are less than $n$. Supposing I can find the prime factorization, it is simple to find the total number of factors as a combinatorial ...
1
vote
1answer
124 views

Interpolation of a sequence of polynomials (viewed in terms of q-analogue powers)

I'm trying to find closed-form expressions for a sequence of coefficients, such that the index of the coefficient occurs as number such that I can later interpolate to fractional indexes as well. ...
4
votes
1answer
403 views

Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors?

Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors? For example, suppose we have $n = p * q = 167653$; in this case, $p = 359 = 101100111_2$ and $q = 467 = ...
2
votes
1answer
95 views

Factoring short intervals

There are algorithms (e.g., SIQS) that factor individual numbers. For large ranges of numbers, sieving is more efficient: for example, $(x^2,x^2+x)$ can be factored in time roughly linear in $x$. ...
3
votes
4answers
924 views

Can $A^2+B^2+C^2-2AB-2AC-2BC$ be a perfect square

I have come upon the equation $A^2+B^2+C^2-2AB-2AC-2BC$ and want to factor it. Because of the symmetry, I am wondering if it can be a perfect square or if there is some other nice factorization.
6
votes
1answer
226 views

Factoring some integer in the given interval

Let N be a positive integer. Is there an efficient (i.e. probabilistic polynomial time) algorithm which, on input a sufficiently large N, outputs the full factorization of some integer in the interval ...
8
votes
4answers
681 views

How to determine in polynomial time if a number is a product of two consecutive primes?

How to determine in polynomial time if a number is a product of two consecutive primes? All I can figure out is that if Cramér's conjecture is true, then we can use the AKS primality test to find ...
2
votes
3answers
80 views

Solving for the interval of time during which the height of a thrown ball is at least “h” feet

In dealing with inequalities I've run into a certain peculiarity which I am currently unable to explain. The example: Find the interval of time during which the ball is at least 32 feet above ground. ...
2
votes
4answers
219 views

Find largest integer $x$ such that $3^x$ is a factor of $27^5$

Is the following solvable using just arithmetic rather than a calculator, and if so, how? Which of the following numbers is the greatest positive integer x such that $3^x$ is a factor of $27^5~$? ...
5
votes
2answers
335 views

Factoring $X^{16}+X$ over $\mathbb{F}_2$

I just asked wolframalpha to factor $X^{16}+X$ over $\mathbb{F}_2$. The normal factorization is $$ X(X+1)(X^2-X+1)(X^4-X^3+X^2-X+1)(X^8+X^7-X^5-X^4-X^3+X+1) $$ and over $GF(2)$ it is $$ ...
2
votes
6answers
261 views

Factoring Quadratics

Is there a method to find which numbers to use when simplifying quadratics? For example $x^2 + 5x + 6$ is easy enough to find, but what if I have bigger numbers, or I have this quadratic expression: ...
1
vote
3answers
139 views

Trigonometric factoring

Very next question, no idea what to do... I am suppose to factor $2\sin^2x + 3\sin x+1$ . I figure this is pretty simple so I do $(2\sin x)(2\sin x)+3 \sin x+1$ . For some reason this is incorrect ...
3
votes
2answers
124 views

Factoring Quantities Question

I was doing an exercise and ran into a problem with their use of factoring. Here is the problem specific to where the issue occurs: $$ \frac{(x^2 + 1)^{1/2} - x^2 (x^2 + 1)^{-1/2}}{x^2 + 1} = ...
6
votes
2answers
487 views

Is the factorization problem harder than RSA factorization ($n = pq$)?

Let $n \in \mathbb{N}$ be a composite number, and $n = pq$ where $p,q$ are distinct primes. Let $F : \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}$ (*) be an algorithm which takes as an input $x ...
2
votes
2answers
128 views

Calculations with liars and sums of prime factors

Suppose you are given a number $n$ and told that the sum of its prime factors is $s$. I'm looking for an efficient algorithm that checks the truth of the statement. Obviously one can simply ...
1
vote
4answers
8k views

Factoring Methods/Tricks

One of the things I've struggled with most in algebra/calculus is all the "factoring tricks". When I take time away from doing math I inevitably forget most if not all of them. The old proverb "use it ...
2
votes
3answers
202 views

Edge of factoring technology?

Schneier in 1996's Applied Cryptography says: "Currently, a 129-decimal-digit modulus is at the edge of factoring technology" In the intervening 15 years has anything much changed?
3
votes
4answers
331 views

Factorize $x^3-3x+2$

How can I factorize $x^3-3x+2$ ? The answer that I got on the internet is $(x-1)^2(x+2)$. It would be nice if anyone could also tell what these type of equations are called and where can I learn ...
2
votes
3answers
941 views

About the factors of the product of prime numbers

If a number is a product of unique prime numbers, are the factors of this number the used unique prime numbers ONLY? Example: 6 = 2 x 3, 15 = 3 x 5. But I don't know for large numbers. I will be using ...
3
votes
1answer
73 views

Techniques for forming square factorizations

Say you have the polynomial $$ x^4 + 2 + x^{-4} $$ Looking at it, you see you can do $$\begin{align*} x^4 + 1 + 1 + x^{-4} & =x^2( x^2 + x^{-2} ) + x^{-2}( x^2 + x^{-2} )\\ &= \left( x^2 + ...
3
votes
2answers
546 views

What's the best way to factor a 256-bit number?

Suppose $N$ is an RSA modulus (ie, it's the product of two distinct primes), 256 bits long. What is the best method to factor it? Trial division is out of the question, Pollard's Rho is probably out ...
21
votes
2answers
1k views

Is factoring polynomials as hard as factoring integers?

There seems to be a consensus that factorization of integers is hard (in some precise computational sense.) Is it known whether polynomial factorization is computationally easy or hard? One thing I ...
0
votes
1answer
234 views

Factoring the polynomial $2x^2 - 2x + 2$

I saw in my book that $2x^2 - 2x + 2$ factored became $2(x^2 - x + 1)$. Why it does not became $2(x(x - 1) + 1)$? Is it wrong or correct as well?
0
votes
1answer
124 views

How did they simplify this function

I'm currently practicing differentiation. The exercise I currently have is the following Find the derivative of: $(x + 6)^3 (9 x^3 - 2)^5$ Okay, well I can do that now. When I do this I uses the ...
3
votes
1answer
233 views

Factoring a trivariate polynomial

I would appreciate some help with factoring a trivariate polynomial. The polynomial in question is $$p(x,y,z)=a_1 x^7+a_2 x^5y+a_3 x^3y^2+a_4 xy^3+a_5 x^4z+a_6 x^2yz+a_7 y^2z+a_8 xz^2,$$ where the ...
0
votes
2answers
556 views

Factoring Multiple Variable Polynomials

This is in relation to a problem dealing with the three-dimensional analogue of Pell's Equation. I would like to factor $ x^3+Dy^3+D^2z^3-3Dxyz $ into $\frac{1}{2}(x+Dy+D^2y)$ and another factor. I ...