如果你也在 怎样代写现代代数Modern Algebra 这个学科遇到相关的难题，请随时右上角联系我们的24/7代写客服。现代代数Modern Algebra就像数学的其他分支一样——只有从最基本的思想和例子中仔细地推导才能掌握。但这需要时间，而且有些目标在你实现之前是不明确的。
现代代数Modern Algebra这门学科的思想和方法几乎渗透到现代数学的每一个部分。此外，没有一门学科更适合培养处理抽象概念的能力，即理解和处理问题或学科的基本要素。这包括阅读数学的能力，提出正确的问题，解决问题，运用演绎推理，以及写出正确、切中要害、清晰的数学。
statistics-lab™ 为您的留学生涯保驾护航 在代写现代代数Modern Algebra方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写现代代数Modern Algebra代写方面经验极为丰富，各种代写现代代数Modern Algebra相关的作业也就用不着说。
数学代写|现代代数代写Modern Algebra代考|Modular ged algorithm in F[x, y]
In Section 6.11, we present a modular algorithm that computes all results of the Extended Euclidean Algorithm, including the gcd and the Bézout coefficients. But if just the gcd is required, there is a better way which we now describe.
In a modular algorithm, say with a big prime $p$, we need two conditions to be satisfied: $p$ has to be large enough so that the coefficients of the gcd can be recovered from their images modulo $p$, and $p$ should not divide the resultant and the leading coefficient of the gcd, so that its degree does not change modulo $p$. When both input polynomials have degree about $n$ and coefficients of length $n$, then the bound for the first condition is $O(n)$, but for the second one it is about $n^2$. The trick now is to choose $p$ randomly so that coefficient recovery is always guaranteed, but the non-divisibility condition only with high probability.
This introduces the important method of probabilistic algorithms. Such an algorithm takes an input, makes some random choices (say, chooses several times a bit, either 0 or 1 , each with equal probability), does some calculations, and returns an output. If one can prove that the probability of returning the correct output is at least some value greater than $1 / 2$, say $2 / 3$, then one can run the algorithm repeatedly, and will obtain the correct answer by a majority vote with probability arbitrarily close to 1 . This is called a Monte Carlo algorithm. In some applications, as in this chapter, one can easily test the output for correctness. Then the error probability becomes zero, and only the running time is a random variable. This is called a Las Vegas algorithm. See Notes 6.5 and Section 25.8 for discussions.
These probabilistic algorithms actually started in computer algebra, with Berlekamp’s polynomial factorization (Section 14.8) and Solovay \& Strassen’s primality test (Section 18.5). Their power and simplicity has made them a ubiquitous tool in many areas of computer science. We have seen examples of probabilistic modular testing in Section 4.1. These methods have an inherent uncertainty, but it can be made arbitrarily small, and thus they are like playing a highly attractive lottery: the stakes are only a tiny fraction of the jackpot (say, polynomial time vs. exponential time), but you are almost guaranteed to win!
数学代写|现代代数代写Modern Algebra代考|Mignotte’s factor bound and a modular gcd algorithm in Z[x]
In order to adapt Algorithm 6.28 to $\mathbb{Z}[x]$, we need an a priori bound on the coefficient size of $h$. Over $F[y]$, the bound
$$
\operatorname{deg}_y h \leq \operatorname{deg}_y f
$$
is trivial and quite sufficient. Over $\mathbb{Z}$, we could use the subresultant bound of Theorem 6.52 below, but we now derive a much better bound. It actually depends only on one argument of the gcd, say $f$, and is valid for all factors of $f$. We will use this again for the factorization of $f$ in Chapter 15 .
We extend the 2-norm to a complex polynomial $f=\sum_{0 \leq i \leq n} f_i x^i \in \mathbb{C}[x]$ by $|f|_2=\left(\sum_{0 \leq i \leq n}\left|f_i\right|^2\right)^{1 / 2} \in \mathbb{R}$, where $|a|=(a \cdot \bar{a})^{1 / 2} \in \mathbb{R}$ is the norm of $a \in \mathbb{C}$ and $\bar{a}$ is the complex conjugate of $a$. We will derive a bound for the norm of factors of $f$ in terms of $|f|_2$, that is, a bound $B \in \mathbb{R}$ such that any factor $h \in \mathbb{Z}[x]$ of $f$ satisfies $|h|_2 \leq B$. One might hope that we can take $B=|f|_2$, but this is not the case. For example, let $f=x^n-1$ and $h=\Phi_n \in \mathbb{Z}[x]$ be the $n$th cyclotomic polynomial (Section 14.10). Thus $\Phi_n$ divides $x^n-1$, and the direct analog of (8) would say that each coefficient of $\Phi_n$ is at most 1 in absolute value, but for example $\Phi_{105}$, of degree 48 , contains the term $-2 x^7$. In fact, the coefficients of $\Phi_n$ are unbounded in absolute value if $n \longrightarrow \infty$, and hence this is also true for $|h|_2$. Worse yet, for infinitely many integers $n, \Phi_n$ has a very large coefficient, namely larger than $\exp (\exp (\ln 2 \cdot \ln n / \ln \ln n))$, where $\ln$ is the logarithm in base $e$; such a coefficient has word length somewhat less than $n$. It is not obvious how to control the coefficients of factors at all, and it is not surprising that we have to work a little bit to establish a good bound.
现代代数代考
数学代写|现代代数代写Modern Algebra代考|Modular ged algorithm in F[x, y]
在第6.11节中，我们给出了一个模块化算法来计算扩展欧几里得算法的所有结果，包括gcd和bsamzout系数。但如果只需要gcd，我们现在描述的是一种更好的方法。
在一个模块化算法中，比如有一个大质数$p$，我们需要满足两个条件:$p$必须足够大，以便gcd的系数可以从其模$p$的图像中恢复，并且$p$不应该除以gcd的结果系数和前导系数，以便它的度不改变模$p$。当两个输入多项式的度数为$n$，系数长度为$n$时，第一种情况的界是$O(n)$，而第二种情况的界是$n^2$。现在的诀窍是随机选择$p$，这样系数恢复总是有保证的，但不可除性条件只有在高概率下才有保证。
介绍了概率算法的重要方法。这样的算法接受输入，做出一些随机选择(比如，选择几次位，要么0，要么1，每个都有相同的概率)，进行一些计算，然后返回一个输出。如果可以证明返回正确输出的概率至少大于$1 / 2$，例如$2 / 3$，那么可以重复运行该算法，并且将通过概率任意接近1的多数投票获得正确答案。这被称为蒙特卡罗算法。在某些应用程序中，如本章所述，可以很容易地测试输出的正确性。此时，错误概率为零，只有运行时间是随机变量。这被称为拉斯维加斯算法。有关讨论，请参见注释6.5和第25.8节。
这些概率算法实际上始于计算机代数，包括Berlekamp的多项式因式分解(第14.8节)和Solovay ＆ Strassen的素数检验(第18.5节)。它们的强大功能和简单性使其成为计算机科学许多领域中无处不在的工具。我们已经在4.1节中看到了概率模块测试的例子。这些方法具有固有的不确定性，但它可以任意小，因此它们就像玩一个非常吸引人的彩票:赌注只是头奖的一小部分(比如，多项式时间vs指数时间)，但你几乎保证会赢!
数学代写|现代代数代写Modern Algebra代考|Mignotte’s factor bound and a modular gcd algorithm in Z[x]
为了使算法6.28适应$\mathbb{Z}[x]$，我们需要对$h$的系数大小有一个先验的界。除以$F[y]$，边界
$$
\operatorname{deg}_y h \leq \operatorname{deg}_y f
$$
是微不足道的，而且是足够的。在$\mathbb{Z}$上，我们可以使用下面定理6.52的次结界，但我们现在推导出一个更好的界。它实际上只依赖于gcd的一个参数，比如$f$，并且对$f$的所有因素都有效。我们将在第15章中再次使用它来分解$f$。
我们通过$|f|2=\left(\sum{0 \leq i \leq n}\left|f_i\right|^2\right)^{1 / 2} \in \mathbb{R}$将2范数扩展到一个复多项式$f=\sum_{0 \leq i \leq n} f_i x^i \in \mathbb{C}[x]$，其中$|a|=(a \cdot \bar{a})^{1 / 2} \in \mathbb{R}$是$a \in \mathbb{C}$的范数，$\bar{a}$是$a$的复共轭。我们将用$|f|2$来推导$f$的因子范数的一个界，即，一个界$B \in \mathbb{R}$使得$f$的任何因子$h \in \mathbb{Z}[x]$满足$|h|_2 \leq B$。有人可能希望我们可以采取$B=|f|_2$，但事实并非如此。例如，设$f=x^n-1$和$h=\Phi_n \in \mathbb{Z}[x]$是$n$的第一个分环多项式(第14.10节)。因此$\Phi_n$除$x^n-1$，与(8)的直接类比会说，$\Phi_n$的每个系数的绝对值最多为1，但例如，次为48的$\Phi{105}$包含了$-2 x^7$项。事实上，$\Phi_n$的系数在$n \longrightarrow \infty$的绝对值上是无界的，因此对于$|h|_2$也是如此。更糟糕的是，对于无穷多个整数$n, \Phi_n$有一个非常大的系数，即大于$\exp (\exp (\ln 2 \cdot \ln n / \ln \ln n))$，其中$\ln$是以$e$为底的对数;该系数的字长略小于$n$。如何控制因子的系数一点也不明显，所以我们需要花点功夫来建立一个好的界也就不足为奇了。
统计代写请认准statistics-lab™. statistics-lab™为您的留学生涯保驾护航。