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

wsc810

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

mathe

这是Pell方程的特殊情况

wsc810

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

mathe

$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

二阶丢番图，$a x^2 + b x y + c y^2 + d x + e y + f = 0$，早就研究成熟了，
论坛里的大侠们也已经多有讨论

楼主还是多看看Pell方程，丢番图方程方面的知识吧，

我虽涉及不深，但对于具体的某一方程，我可以随时给出其一般解，嘿嘿。。。

wsc810

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

wayne

，我其实很弱的。。。我只会捣鼓软件

你给的这个方程其判别式不是一个平方数，所以，可以转化成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

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

wsc810

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

mathe

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