怎样使二次函数的值为平方数

wsc810 · 发表于 2009-9-5 10:43:20

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

求使下式成立的x,y Qx*x-2Px-Q'=y*y 其中，Q,P,Q'为已知数，判别式的值可令为4D，D为待分解的数,希望牛人能给出答案，该问题对大合数分解有帮助。

mathe · 发表于 2009-9-5 11:10:03

这是Pell方程的特殊情况

wsc810 · 发表于 2009-9-5 15:05:06

本帖最后由 wsc810 于 2009-9-5 15:14 编辑 mathe说的话我怎么不太理解呀，能详细解释下么。按照Pell方程，P*P=-Q*Q'(mod D),这里的特殊情形为Q或Q'为平方数，则有p_n£2=(-1)£n*Q_(n+1)(mod D),这与题中提到的可是两回事呀！

mathe · 发表于 2009-9-5 17:32:03

$Q^2*x^2-2PQx-Q Q'=Qy^2$ $(Qx-P)^2-P^2-Q Q'=Qy^2$ 记$X=Qx-P$ 于是转化为Pell方程$X^2-Qy^2=P^2+Q Q'$,当然还有特殊约束$X-=-P(mod Q)$

wayne · 发表于 2009-9-5 17:35:23

本帖最后由 wayne 于 2009-9-5 17:36 编辑 二阶丢番图，$a x^2 + b x y + c y^2 + d x + e y + f = 0$，早就研究成熟了，论坛里的大侠们也已经多有讨论楼主还是多看看Pell方程，丢番图方程方面的知识吧，我虽涉及不深，但对于具体的某一方程，我可以随时给出其一般解，嘿嘿。。。

wsc810 · 发表于 2009-9-5 18:18:26

楼上可否解一下我给的方程 7x~2-2*60x-83=y~2,希望写出具体过程，让新人学习学习。多谢！

wayne · 发表于 2009-9-5 20:13:42

，我其实很弱的。。。我只会捣鼓软件你给的这个方程其判别式不是一个平方数，所以，可以转化成Pell方程。我用软件运行了一下，得到x<10^100的正整数解有330组，x<10^1000的正整数解有3325组前20组是： (18, 5), (21, 22), (42, 85), (69, 158), (99, 238), (174, 437), (531, 1382), (966, 2533), (1446, 3803), (2643, 6970), (8334, 22027), (15267, 40370), (22917, 60610), (41994, 111083), (132693, 351050), (243186, 643387), (365106, 965957), (669141, 1770358), (2114634, 5594773), (3875589, 10253822) 第3325组是： {908588057726682407266465373953961220585525125189156111545738673120099\ 7962865669182175486631411127995676636039540053279783870365628894186800\ 4410187664292121619679552716301709215359543697342181004855513821346190\ 7594276561789819185750149450149055190166845732846067057172322194227180\ 6981232642996083986074336609724915695573345715050622955252618424676831\ 1936120594154820988432181043338860236293586049367801261932762489180024\ 2745500135551707628635588665596887046333631334505478362696985501239260\ 7481399241042615153334551749657506986550707136518451843556907556311920\ 1212721727445768270621246087532439144700711421908369357339382217965743\ 0030023826060017290250615473903980583619671807213976249969147420496564\ 6903588136336329650993411767902134576324452308930116882306067253322877\ 8801153832400360492648292406194943488600860113987896041007699080817354\ 7527470122814115821407610036039250379112998784213041167926695712776665\ 6585953204760807248848128920994076642835725347955484404804792492726272\ 115633445783143195717, \ 2403898044947999897877169248226961091216007517020338239725624858558539\ 3401693610871284028795695063899453866846378945934145565154482433528211\ 7055848857494231206029370482230177642587674448284228584064896981166970\ 9310395598263920208647829903422239157061492763528956535879235686854362\ 5366159315354193704393767642904016714315547090890317912869621417358449\ 7884981459226852870769496288635063604506848927110088844857891571641134\ 7548058986253878307361473094377977993222806862131831602189024976453365\ 1810010491078815442298756654165958785608776514418100241245927945890573\ 3933055569808337908038580732542612884471886560985146672553904892276606\ 4613673204593916765915087309069254939256738352588171821878725021803992\ 0525219990717603336999503280156572929772808205649800980858290973098546\ 5859411566653557870679056061921173796762110967156892621416079330826972\ 6355019519888803088649887744429801092199889008978365578827219511736720\ 4925037621276423513524901573379418827641862651569453544479749991734772\ 003637909683938794850}

wayne · 发表于 2009-9-5 20:27:36

上面的这么多的解其实可以用线性方程递推： x(n)=x(n-1)+16x(n-4)-16x(n-5)-x(n-8)+x(n-9) .....

wsc810 · 发表于 2009-9-5 21:27:43

在这里我们只关心最小解。你用计算机可以搜索到10~1000内的值，而RSA所用到的大合数才不过200位到300位，不知道用它来计算Q在小于2sqrt(D)时的数成不成问题，若是的话，计算的难点是什么？我想请教mathe,解这种方程的一般方法是什么，软件又是如何解决这种特殊的Pell方程的。

mathe · 发表于 2009-9-6 18:53:15

你看一下论坛里面Pell方程相关的一些帖子吧.可以查看1#左上角的链接

账号		自动登录	找回密码
密码			欢迎注册

[分享] 怎样使二次函数的值为平方数

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。