大数分解，已知N和p小于q，设计不依赖第三方库的python代码求p

这是一个经典的大数分解问题，可以使用Pollard-Rho算法来解决。下面是一个不依赖第三方库的Python代码实现：

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def pollard_rho(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return 2
    x = 2
    y = 2
    d = 1
    while d == 1:
        x = (x * x + 1) % n
        y = (y * y + 1) % n
        y = (y * y + 1) % n
        d = gcd(abs(x - y), n)
    if d == n:
        return pollard_rho(n)
    else:
        return d

n = 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
q = 123456789101112131415161718192021222324252627282930313233343536373839404142434445
p = n // q
while True:
    if n % p == 0:
        break
    else:
        p = pollard_rho(n // q)
print(p)

代码中，我们先通过q计算出p的初始值，然后不断进行大数分解，直到p能够整除n。在分解过程中，我们使用了Pollard-Rho算法来快速找到p的一个因子。

希望我的回答能够帮助到你。