Perhaps you meant this ( but it takes quite a time, at least on my machine and version (Mathematica 7))
n = 694731678205117652428301338831622311963738931724625729473216810092\
7685542953186877088247405474227499941878119619112835060529063890728108\
5633288937673680524199820066895936872314770237447995716771439959238004\
2734866537704895198840871845612559330867293160058938830527965899687220\
7565635750796837886900524108916568983753877594647065444649950196607661\
4890157622775988094202464078929288907735084091176712819439586018201262\
5846753305993032317996513280746345443850444194767550769852516360842192\
6832808008825166204369886645452308473163980254476581701503785258358004\
5461950139773968906062830312323507628556726568436388771648582054725350\
5554399528710141069500293986050022266286622854370337793185515367472943\
7495225549647268078066582645736689625022024986695409941985639778625818\
0576705276869616498812031948075619511682529816958383878485379938346995\
2263139847120378924111865243903708300981964894526223893237201955861687\
6551724529760107034639682805477991546353067110867193605317560595799443\
6181065402719501539141;
sq = Table[j, {j, 10000}];
b = Select[sq, PrimeQ, 1000];
n1 = (n^2 - 1);
Catch[
Do[
If[PrimeQ[n1 + b[[i]]], Throw[b[[i]]]],
{i, 1, Length[b]}
]]