Faits :
Faits :
A. X._ est né en 1981 en Algérie. Il a déposé une demande d'asile en 2002 à Vallorbe. Attribué au canton de Zurich, il y a vécu quatre mois, avant de gagner Lausanne. Il a séjourné de manière illégale sur territoire vaudois, puis à Monthey, durant environ deux ans. Dans le courant 2004, il a vécu auprès d'une bénéficiaire d'une rente invalidité puis, vers fin avril 2005, suite à un ordre de renvoi, il est rentré en Algérie où il vit chez ses parents, qui l'entretiennent.
A. X._ est né en 1981 en Algérie. Il a déposé une demande d'asile en 2002 à Vallorbe. Attribué au canton de Zurich, il y a vécu quatre mois, avant de gagner Lausanne. Il a séjourné de manière illégale sur territoire vaudois, puis à Monthey, durant environ deux ans. Dans le courant 2004, il a vécu auprès d'une bénéficiaire d'une rente invalidité puis, vers fin avril 2005, suite à un ordre de renvoi, il est rentré en Algérie où il vit chez ses parents, qui l'entretiennent.
B. A._, née en 1982, présentait des difficultés scolaires et d'apprentissage. Elle a bénéficié de prestations de l'assurance-invalidité afin de terminer sa formation, en juillet 2002, auprès d'un Centre de formation professionnelle et sociale (CFPS). Selon un rapport de cet établissement, la jeune fille, très timide et introvertie, a profité de son séjour pour progresser sur le plan personnel. Elle a pris conscience de son manque de confiance en elle, mais a conservé malgré tout une certaine fragilité. Sur le plan pratique, son apprentissage a été entravé par d'importantes limitations cognitives. En cas de stress et de surstimulation notamment, elle perdait ses moyens et ne parvenait pas à fonctionner adéquatement.
B. A._, née en 1982, présentait des difficultés scolaires et d'apprentissage. Elle a bénéficié de prestations de l'assurance-invalidité afin de terminer sa formation, en juillet 2002, auprès d'un Centre de formation professionnelle et sociale (CFPS). Selon un rapport de cet établissement, la jeune fille, très timide et introvertie, a profité de son séjour pour progresser sur le plan personnel. Elle a pris conscience de son manque de confiance en elle, mais a conservé malgré tout une certaine fragilité. Sur le plan pratique, son apprentissage a été entravé par d'importantes limitations cognitives. En cas de stress et de surstimulation notamment, elle perdait ses moyens et ne parvenait pas à fonctionner adéquatement.
C. Le 14 mai 2004, A._, s'est présentée au poste de gendarmerie de Monthey pour dénoncer une infraction contre son intégrité sexuelle commise au début de l'année 2003. Elle a expliqué qu'elle avait fait la connaissance de X._ dix-huit mois auparavant, sur le trajet entre Monthey et Champéry, alors qu'elle rentrait chez elle en train. L'individu aurait engagé la conversation et l'aurait suivie à Champéry, bien qu'elle ait insisté pour qu'il la laisse tranquille. Elle aurait à nouveau rencontré cet individu par hasard une semaine plus tard dans un bar à Monthey alors qu'elle était accompagnée d'une amie. Elle aurait signifié à X._ qu'elle ne désirait pas être abordée, mais ce dernier l'aurait tout de même suivie jusqu'à son lieu de travail, à Monthey. Comme elle ne lui répondait pas, il lui aurait dit qu'il la taperait si elle ne faisait pas ce qu'il voulait. Aux abords de son lieu de travail, il lui aurait demandé dix francs, qu'elle lui aurait donnés. Quelque temps après, X._ l'aurait attendue à midi devant son lieu de travail et l'aurait invitée à prendre un verre chez lui, ce qu'elle aurait refusé dans un premier temps. X._ aurait insisté, se serait un peu énervé, aurait saisi la jeune fille par l'avant-bras gauche et l'aurait tirée contre lui. Devant une telle insistance et mue par la peur d'éventuelles représailles, A._ aurait finalement cédé sans appeler au secours ni chercher à fuir. X._ l'aurait conduite à son studio. Une fois à l'intérieur, il aurait fermé la porte à clef avant de proposer un verre à la jeune fille et de l'inviter à s'asseoir sur le bord du lit à ses côtés. A._ s'y serait refusée et aurait constaté que la serrure était verrouillée. X._ l'aurait saisie par le bras en la rassurant, lui aurait demandé de se coucher sur le lit et se serait assis sur elle en la chevauchant. Il l'aurait déshabillée puis se serait dévêtu avant de saisir un préservatif sur une étagère. A._ aurait eu peur. X._ lui aurait caressé le sexe puis aurait enfilé le préservatif avant de la pénétrer, difficilement, en lui faisant mal. Elle était vierge et la pénétration lui aurait occasionné des saignements. Elle aurait tenté en vain de le repousser des pieds et des mains tout en le suppliant d'arrêter. X._ l'aurait plusieurs fois embrassée sur la bouche et sur la poitrine, qu'il aurait aussi caressée, puis se serait retiré pour enlever le préservatif et éjaculer sur le lit. la jeune femme se serait ensuite rhabillée et aurait pu quitter les lieux après avoir longuement insisté, puis serait retournée au travail. Dans le courant 2003 et jusqu'aux environs de fin avril 2004, X._ aurait provoqué plusieurs fois des rencontres avec elle. A plusieurs reprises, cet homme, dont elle avait peur, lui aurait demandé de l'argent. Il aurait ainsi obtenu au moins 100 francs, ce qui aurait privé la jeune fille de l'argent nécessaire pour s'acheter à manger et l'aurait amenée à voler, à raison de 1 ou 2 francs chaque fois, de l'argent à une collègue. A._ a expliqué qu'elle était de nature timide et réservée et qu'elle ne parlait pas facilement avec sa famille et ses amis. Elle a dit n'avoir pas osé dénoncer X._ plus tôt parce qu'elle avait peur qu'il ne lui arrive quelque chose et ne l'a fait que lorsqu'elle a été accusée de vol par sa collègue et risquait ainsi de perdre sa place de travail.
C. Le 14 mai 2004, A._, s'est présentée au poste de gendarmerie de Monthey pour dénoncer une infraction contre son intégrité sexuelle commise au début de l'année 2003. Elle a expliqué qu'elle avait fait la connaissance de X._ dix-huit mois auparavant, sur le trajet entre Monthey et Champéry, alors qu'elle rentrait chez elle en train. L'individu aurait engagé la conversation et l'aurait suivie à Champéry, bien qu'elle ait insisté pour qu'il la laisse tranquille. Elle aurait à nouveau rencontré cet individu par hasard une semaine plus tard dans un bar à Monthey alors qu'elle était accompagnée d'une amie. Elle aurait signifié à X._ qu'elle ne désirait pas être abordée, mais ce dernier l'aurait tout de même suivie jusqu'à son lieu de travail, à Monthey. Comme elle ne lui répondait pas, il lui aurait dit qu'il la taperait si elle ne faisait pas ce qu'il voulait. Aux abords de son lieu de travail, il lui aurait demandé dix francs, qu'elle lui aurait donnés. Quelque temps après, X._ l'aurait attendue à midi devant son lieu de travail et l'aurait invitée à prendre un verre chez lui, ce qu'elle aurait refusé dans un premier temps. X._ aurait insisté, se serait un peu énervé, aurait saisi la jeune fille par l'avant-bras gauche et l'aurait tirée contre lui. Devant une telle insistance et mue par la peur d'éventuelles représailles, A._ aurait finalement cédé sans appeler au secours ni chercher à fuir. X._ l'aurait conduite à son studio. Une fois à l'intérieur, il aurait fermé la porte à clef avant de proposer un verre à la jeune fille et de l'inviter à s'asseoir sur le bord du lit à ses côtés. A._ s'y serait refusée et aurait constaté que la serrure était verrouillée. X._ l'aurait saisie par le bras en la rassurant, lui aurait demandé de se coucher sur le lit et se serait assis sur elle en la chevauchant. Il l'aurait déshabillée puis se serait dévêtu avant de saisir un préservatif sur une étagère. A._ aurait eu peur. X._ lui aurait caressé le sexe puis aurait enfilé le préservatif avant de la pénétrer, difficilement, en lui faisant mal. Elle était vierge et la pénétration lui aurait occasionné des saignements. Elle aurait tenté en vain de le repousser des pieds et des mains tout en le suppliant d'arrêter. X._ l'aurait plusieurs fois embrassée sur la bouche et sur la poitrine, qu'il aurait aussi caressée, puis se serait retiré pour enlever le préservatif et éjaculer sur le lit. la jeune femme se serait ensuite rhabillée et aurait pu quitter les lieux après avoir longuement insisté, puis serait retournée au travail. Dans le courant 2003 et jusqu'aux environs de fin avril 2004, X._ aurait provoqué plusieurs fois des rencontres avec elle. A plusieurs reprises, cet homme, dont elle avait peur, lui aurait demandé de l'argent. Il aurait ainsi obtenu au moins 100 francs, ce qui aurait privé la jeune fille de l'argent nécessaire pour s'acheter à manger et l'aurait amenée à voler, à raison de 1 ou 2 francs chaque fois, de l'argent à une collègue. A._ a expliqué qu'elle était de nature timide et réservée et qu'elle ne parlait pas facilement avec sa famille et ses amis. Elle a dit n'avoir pas osé dénoncer X._ plus tôt parce qu'elle avait peur qu'il ne lui arrive quelque chose et ne l'a fait que lorsqu'elle a été accusée de vol par sa collègue et risquait ainsi de perdre sa place de travail.
D. Après avoir menti sur son identité à la police et nié devant elle et devant le juge d'instruction savoir qui était A._, X._ a admis devant ce dernier la connaître pour avoir discuté avec elle une fois dans le train alors qu'il se rendait à Champéry. Bien qu'il avait reconnu devant la police avoir logé dans le studio désigné par A._, il a contesté ce fait devant le juge, disant que c'était un ressortissant italien qui y logeait et que c'est ce dernier qui avait emmené A._ chez lui, avait partagé un verre avec elle, lui avait même prêté dix francs et remis une bouteille d'eau, ce qu'a contesté A._.
D. Après avoir menti sur son identité à la police et nié devant elle et devant le juge d'instruction savoir qui était A._, X._ a admis devant ce dernier la connaître pour avoir discuté avec elle une fois dans le train alors qu'il se rendait à Champéry. Bien qu'il avait reconnu devant la police avoir logé dans le studio désigné par A._, il a contesté ce fait devant le juge, disant que c'était un ressortissant italien qui y logeait et que c'est ce dernier qui avait emmené A._ chez lui, avait partagé un verre avec elle, lui avait même prêté dix francs et remis une bouteille d'eau, ce qu'a contesté A._.
E. Selon le rapport de la Dresse B._, spécialiste en gynécologie et obstétrique, A._ l'a consultée pour la première fois le 9 octobre 2003. La patiente lui a dit qu'elle était vierge. Lorsqu'elle l'a revue le 18 mai 2004, elle lui a déclaré avoir été, une année auparavant, victime d'un viol perpétré par un marocain rencontré dans le train. Elle n'avait pas eu d'autres relations après cet épisode violent. Elle lui a dit que cet homme lui demandait également régulièrement de l'argent et que pour le satisfaire elle s'était mise à voler sur son lieu de travail. Selon les observations du médecin, l'hymen de la patiente était encore bien présent avec une déchirure à 05h00. Ce status était compatible avec une pénétration, voire une ou deux autres, mais pas avec des relations régulières.
E. Selon le rapport de la Dresse B._, spécialiste en gynécologie et obstétrique, A._ l'a consultée pour la première fois le 9 octobre 2003. La patiente lui a dit qu'elle était vierge. Lorsqu'elle l'a revue le 18 mai 2004, elle lui a déclaré avoir été, une année auparavant, victime d'un viol perpétré par un marocain rencontré dans le train. Elle n'avait pas eu d'autres relations après cet épisode violent. Elle lui a dit que cet homme lui demandait également régulièrement de l'argent et que pour le satisfaire elle s'était mise à voler sur son lieu de travail. Selon les observations du médecin, l'hymen de la patiente était encore bien présent avec une déchirure à 05h00. Ce status était compatible avec une pénétration, voire une ou deux autres, mais pas avec des relations régulières.
F. Dans un rapport du 24 janvier 2005, C._, psychologue-psychothérapeute FSP, relève qu'elle a diagnostiqué chez sa patiente le 15 juin 2004 un état de stress post-traumatique. Lors du processus thérapeutique (traitement sous hypnose ericksonienne non suggestive) la patiente a revu des détails liés à l'agression qui permettaient de confirmer que cette dernière a effectivement été vécue et n'était pas le fruit de son imagination. Selon la psychologue, la patiente s'est trouvée agressée probablement en raison d'une naïveté certaine et d'un manque de discernement vis-à-vis des intentions malsaines de son agresseur à son égard et qui n'ont pas pu être perçues par elle. Avec ses repères familiaux, ses valeurs, son vécu et sa personnalité, elle n'avait pas les "outils" pour évaluer et agir dans cette situation en se protégeant adéquatement.
F. Dans un rapport du 24 janvier 2005, C._, psychologue-psychothérapeute FSP, relève qu'elle a diagnostiqué chez sa patiente le 15 juin 2004 un état de stress post-traumatique. Lors du processus thérapeutique (traitement sous hypnose ericksonienne non suggestive) la patiente a revu des détails liés à l'agression qui permettaient de confirmer que cette dernière a effectivement été vécue et n'était pas le fruit de son imagination. Selon la psychologue, la patiente s'est trouvée agressée probablement en raison d'une naïveté certaine et d'un manque de discernement vis-à-vis des intentions malsaines de son agresseur à son égard et qui n'ont pas pu être perçues par elle. Avec ses repères familiaux, ses valeurs, son vécu et sa personnalité, elle n'avait pas les "outils" pour évaluer et agir dans cette situation en se protégeant adéquatement.
G. Le 2 juin 2005, le Tribunal du IIIème arrondissement pour le district de Monthey, en l'absence du prévenu, a reconnu X._ coupable d'extorsion (<ref-law>), de viol (<ref-law>), de faux dans les certificats, de circulation sans permis de conduire et d'usage abusif de permis. Partant, il l'a condamné à trois ans de réclusion, peine complémentaire à celle de trois mois d'emprisonnement prononcée le 25 juillet 2004, à l'expulsion du territoire suisse pour une durée de huit ans et à payer 10'000 fr. à titre d'indemnité pour tort moral à A._.
G. Le 2 juin 2005, le Tribunal du IIIème arrondissement pour le district de Monthey, en l'absence du prévenu, a reconnu X._ coupable d'extorsion (<ref-law>), de viol (<ref-law>), de faux dans les certificats, de circulation sans permis de conduire et d'usage abusif de permis. Partant, il l'a condamné à trois ans de réclusion, peine complémentaire à celle de trois mois d'emprisonnement prononcée le 25 juillet 2004, à l'expulsion du territoire suisse pour une durée de huit ans et à payer 10'000 fr. à titre d'indemnité pour tort moral à A._.
H. L'appel de X._ a été rejeté le 26 octobre 2006 par la Cour pénale II du Tribunal cantonal valaisan.
H. L'appel de X._ a été rejeté le 26 octobre 2006 par la Cour pénale II du Tribunal cantonal valaisan.
I. X._ forme un recours de droit public et un pourvoi en nullité contre cet arrêt. Il conclut à son annulation avec suite de frais et dépens. Il sollicite également l'assistance judiciaire pour les deux procédures.
La Cour pénale II du Tribunal cantonal n'a pas formulé d'observations et s'est référée aux considérants de l'arrêt attaqué.

Le Tribunal fédéral considère en droit:
Le Tribunal fédéral considère en droit:
1. L'arrêt attaqué a été rendu avant l'entrée en vigueur, le 1er janvier 2007, de la loi fédérale du 17 juin 2004 sur le Tribunal fédéral (LTF; RS 173.110). Or, conformément à l'<ref-law>, cette loi ne s'applique aux procédures de recours que si l'acte attaqué a été rendu après son entrée en vigueur. C'est donc sur la base de l'ancien droit de procédure, en l'espèce les art. 84 ss OJ pour le recours de droit public et 268 ss PPF concernant le pourvoi en nullité, que doit être tranchée la présente cause.
En outre, le 1er janvier 2007 sont également entrées en vigueur les nouvelles dispositions de la partie générale du code pénal. Toutefois, celles-ci ne sont pas non plus applicables puisque le Tribunal fédéral saisi d'un pourvoi en nullité examine uniquement la question de savoir si l'autorité cantonale a correctement appliqué le droit fédéral (art. 269 al. 1 PPF), savoir celui qui était en vigueur au moment où elle a statué (<ref-ruling> consid. 5.3 p. 51 s. et les arrêts cités).
I. Recours de droit public
I. Recours de droit public
2. 2.1 Le recours de droit public au Tribunal fédéral est ouvert contre une décision cantonale pour violation de droits constitutionnels des citoyens (art. 84 al. 1 let. a OJ). Il n'est en revanche pas ouvert pour se plaindre d'une violation du droit fédéral, qui peut donner lieu à un pourvoi en nullité (art. 269 al. 1 PPF). Un tel grief ne peut donc pas être invoqué dans le cadre d'un recours de droit public, qui est subsidiaire (art. 84 al. 2 OJ; art. 269 al. 2 PPF).
2.2 Conformément à l'art. 90 al. 1 let. b OJ, l'acte de recours doit, sous peine d'irrecevabilité, contenir un exposé succinct des droits constitutionnels ou des principes juridiques violés et préciser en quoi consiste la violation. Ainsi, le Tribunal fédéral n'a pas à vérifier lui-même si la décision attaquée est en tous points conforme au droit ou à l'équité. Il n'examine que les griefs d'ordre constitutionnel invoqués et suffisamment motivés dans l'acte de recours. Le recourant ne peut se contenter de soulever de vagues griefs ou de renvoyer aux actes cantonaux (<ref-ruling> consid. 1.3 p. 261 s.; <ref-ruling> consid. 1.6 p. 189, 113 consid. 2.1 p. 120). Le Tribunal fédéral n'entre pas non plus en matière sur les critiques de nature appellatoire (<ref-ruling> consid. 1b p. 495).
2.2 Conformément à l'art. 90 al. 1 let. b OJ, l'acte de recours doit, sous peine d'irrecevabilité, contenir un exposé succinct des droits constitutionnels ou des principes juridiques violés et préciser en quoi consiste la violation. Ainsi, le Tribunal fédéral n'a pas à vérifier lui-même si la décision attaquée est en tous points conforme au droit ou à l'équité. Il n'examine que les griefs d'ordre constitutionnel invoqués et suffisamment motivés dans l'acte de recours. Le recourant ne peut se contenter de soulever de vagues griefs ou de renvoyer aux actes cantonaux (<ref-ruling> consid. 1.3 p. 261 s.; <ref-ruling> consid. 1.6 p. 189, 113 consid. 2.1 p. 120). Le Tribunal fédéral n'entre pas non plus en matière sur les critiques de nature appellatoire (<ref-ruling> consid. 1b p. 495).
3. Le recourant invoque une violation de l'interdiction de l'arbitraire consacré par l'art. 9 Cst. Il reproche à l'autorité cantonale d'avoir privilégié la version de la victime au détriment de la sienne. Il constate que les premiers juges ont considéré qu'il avait menti à plusieurs reprises sur son identité et que, partant, ses dénégations s'agissant du viol et de l'extorsion ne pouvaient être crédibles. Il reproche aux juges cantonaux de ne pas avoir porté un regard critique sur les déclarations de la victime.
3.1 Lorsque le recourant prétend que l'on voit mal en quoi le fait d'être privé de la somme modique journalière de 1 ou 2 fr. aurait amené la victime à ne pas pouvoir manger à sa faim, il ne fait qu'opposer sa propre interprétation des faits à celle retenue par l'autorité cantonale, sans aucunement démontrer en quoi l'appréciation de cette autorité et le raisonnement suivi par celle-ci et motivé par les éléments qu'elle cite serait arbitraire. Il en est de même dans la mesure où le recourant soutient qu'on comprend mal pourquoi la victime a accepté de le suivre dans son appartement, alors qu'elle avait compris lors de leur première rencontre qu'il la "draguait", que le recourant ne l'a aucunement violentée et que le seul fondement de son comportement est une peur qu'elle s'est imaginée. Son grief ne répond pas sur ces points aux exigences de motivation de l'art. 90 al. 1 let. b OJ et il n'y a pas lieu de l'examiner.
3.2 Le recourant prétend qu'il y a lieu de se demander comment il a pu enlever les vêtements de sa victime, notamment son jeans par-dessus ses chaussures, en la chevauchant alors qu'elle se débattait. Selon lui, le viol était matériellement impossible.
Une nouvelle fois, il ne fait qu'opposer sa propre appréciation des faits à celle de l'autorité cantonale. En effet, comme l'a relevé celle-ci, le comportement de la victime et ses réactions face à la situation sont parfaitement compréhensibles et explicables, étant donné sa personnalité et son caractère, ainsi que la peur que lui inspirait à juste titre son agresseur. Dans ces circonstances, admettre que le recourant a pu la déshabiller dans les conditions décrites par la victime n'est en rien insoutenable et le recourant ne démontre pas le contraire.
3.3 La cour cantonale a admis que les réactions de la victime, que ce soit notamment à la suite des diverses rencontres avec le recourant ou après le rapport sexuel forcé, apparaissent crédibles et compatibles avec les considérations émises par des tiers ayant été en contact avec l'intéressée, notamment le CFPS et C._.
Le recourant conteste que les premiers juges aient pu expliquer l'attitude de la victime par ses déficiences intellectuelles. Ce serait en contradiction avec les déclarations de la victime, qui aurait indiqué à la police lors de sa première audition qu'elle avait compris que le recourant la "draguait", ce qui démontrerait clairement que c'est en connaissant les intentions du recourant, et non par naïveté, qu'elle l'aurait suivi dans son studio.
Cependant, le fait que la victime ait déclaré avoir compris que le recourant la "draguait" lors de leur première rencontre dans le train ne permet pas de qualifier d'insoutenable l'appréciation que les juges cantonaux ont fait de son comportement ultérieur, notamment le fait qu'elle n'ait pas perçu les intentions malsaines du recourant le jour des faits incriminés, appréciation qui s'appuie sur les constatations de professionnels.
3.4 Le recourant conteste que les premiers juges puissent tirer du fait qu'il n'a pas contesté la description faite par la victime des lieux où se serait déroulé le viol la conclusion qu'il l'a admis implicitement, alors qu'aucune photo ne figure au dossier et qu'aucune visite des lieux n'a été ordonnée.
Cependant, l'appréciation de l'autorité cantonale est étayée par le fait que la victime a pu mentionner l'adresse exacte du recourant, ce qu'elle aurait dû ignorer si, comme le prétendait le recourant, il ne l'y avait pas emmenée, que le recourant a de prime abord reconnu avoir habité ce studio, avant de se rétracter, qu'il n'a jamais prétendu dans ses dénégations que la description du studio n'était pas conforme à la réalité et qu'au contraire il a souligné qu'elle était sommaire et caractéristique de tous les locatifs, admettant ainsi implicitement qu'elle était exacte. Cette appréciation n'est pas insoutenable, même en l'absence de visite des lieux ou de dossier photographique et le recourant ne démontre pas le contraire.
3.5 Le recourant prétend encore qu'on peut se demander si le viol ne s'est pas produit après le 9 octobre 2003, dans la mesure où, à cette date, la victime a consulté la Dresse B._ qui n'aurait constaté alors aucune déchirure de l'hymen, déchirure qu'elle n'a vue que lors de la consultation du 18 mai 2004.
Les simples affirmations du recourant sont contredites par le certificat médical de la Dresse B._ du 24 août 2004, qui dit expressément qu'elle n'a fait aucun examen gynécologique le 9 octobre 2003 et qu'elle n'en a pratiqué un que le 18 mai 2004 après que sa patiente lui ai parlé du viol. Il n'y a donc pas lieu de s'y attarder.
3.6 Le recourant invoque une interprétation arbitraire de l'art. 83bis CCP/VS. En n'obligeant pas le dénommé D._ à témoigner, alors qu'il n'était pas en droit de le refuser, le tribunal cantonal aurait fait preuve d'arbitraire et aurait empêché le recourant de faire valoir un moyen de preuve. Il reprend également le même grief en invoquant cette fois une violation de son droit d'être entendu et notamment celui de fournir des preuves. Il reproche au juge d'instruction d'avoir clôturé l'enquête sans avoir entrepris quelque démarche que ce soit en vue de procéder à l'audition du dénommé D._ et à la cour cantonale d'avoir permis à celui-ci de ne pas s'exprimer, privant ainsi le recourant de faire valoir ses moyens de preuve.
Il ressort cependant du dossier que, suite à la demande du recourant, le juge d'instruction avait décerné un mandat de comparution à l'encontre du dénommé D._ pour être entendu en qualité de témoin. Cet individu étant introuvable à l'adresse indiquée et dans les registres téléphoniques, le juge a demandé au recourant de lui fournir une adresse plus précise, faute de quoi il renoncerait à cette audition. Le recourant n'a pas réagi à cette lettre et n'a pas requis l'audition du dénommé D._ aux débats, pas plus qu'il ne s'est plaint de son défaut d'audition. Il n'est dès lors plus recevable à invoquer une violation de son droit d'être entendu devant le Tribunal fédéral (cf. notamment <ref-ruling> consid. 1a p. 91; <ref-ruling> consid. 2a p. 495), d'autant plus que l'individu susmentionné a été convoqué en procédure d'appel. En effet, dans cette procédure, le recourant a réitéré sa demande d'audition du dénommé D._ "bien connu des services de police en tant qu'il avait fait l'objet le mois précédent d'une interpellation", sans préciser en quelle qualité il souhaitait le faire entendre. Convoqué en tant que personne entendue à titre de renseignement, le dénommé D._ a été rendu attentif à son droit de refuser de témoigner (art. 83bis, 85 et 86 CPP/VS). Celui-ci, après avoir dit qu'il s'inquiétait pour l'avenir de son statut de séjour en Suisse, a refusé de répondre. La présidente a prononcé la clôture de l'instruction, sans qu'il n'apparaisse au procès-verbal d'audience que le recourant ait exigé à quelque moment que ce soit d'entendre le dénommé D._ en qualité de témoin. On peut dès lors se demander si le recourant peut encore se plaindre du fait que le dénommé D._ n'ait pas été entendu en cette qualité. Au demeurant, en décidant de l'auditionner en qualité de personne appelée à fournir des renseignements, du moment qu'il était mis en cause par le recourant, et en lui reconnaissant le droit de s'abstenir de répondre après l'avoir avisé de son droit de refuser de témoigner, même sans indiquer de motifs (cf. art. 83bis ch. 3 CPP/VS et Piquerez, Procédure pénale suisse, 2ème éd., Zurich, Bâle, Genève 2007, n° 566, p. 389), l'autorité cantonale n'a pas fait une interprétation insoutenable du droit cantonal et le recourant ne démontre pas le contraire. Finalement, en donnant suite à son offre de preuve en procédure d'appel, dans les formes prescrites par le droit cantonal, l'autorité cantonale n'a à l'évidence pas violé le droit d'être entendu du recourant. S'ils sont recevables, les griefs du recourant ne peuvent qu'être rejetés.
3.7 Le recourant invoque encore une violation de la présomption d'innocence en tant que règle sur le fardeau de la preuve. Son grief revient en réalité à s'en prendre à l'appréciation des preuves qui a été faite. En effet, considérer que la version de la victime est crédible sur la base d'une analyse de celle-ci ainsi que du dossier et que les dénégations du recourant ne le sont pas, notamment en raison de ses mensonges, ne constitue pas un renversement du fardeau de la preuve, mais une appréciation des preuves.
Le recourant invoque une violation de la présomption d'innocence et renvoie aux motifs qu'il a développés quant à l'arbitraire de la décision attaquée pour démontrer les doutes qu'aurait dû éprouver l'autorité cantonale. Le grief de violation de la présomption d'innocence et le principe "in dubio pro reo" qui en est le corollaire, en tant que règles sur le fardeau de la preuve n'offrent pas, dans la procédure du recours de droit public, de protection plus étendue que l'interdiction d'une appréciation arbitraire des preuves garantie par l'art. 9 Cst. (<ref-ruling> consid. 2 p. 33), qui a déjà été examinée ci-dessus et sur laquelle il n'y a pas lieu de revenir, le recourant ne motivant aucun aspect nouveau de ce grief.
3.8 Le recourant invoque finalement une interprétation arbitraire de l'<ref-law>. En réalité, il reproche à l'autorité cantonale de lui avoir infligé une peine excessive. Son grief revient à se plaindre d'une violation de l'<ref-law>. Or, une telle violation ne peut faire l'objet d'un recours de droit public (art. 84 al. 2 OJ), mais doit être soulevée dans un pourvoi en nullité (art. 269 al. 1 PPF).
Le recours de droit public ne peut qu'être rejeté dans la mesure où il est recevable.
II. Pourvoi en nullité
II. Pourvoi en nullité
4. 4.1 Le pourvoi en nullité à la Cour de cassation pénale du Tribunal fédéral, qui revêt un caractère purement cassatoire (art. 277ter al. 1 PPF), ne peut être formé que pour violation du droit fédéral, à l'exception de la violation directe d'un droit de rang constitutionnel (art. 269 PPF). La Cour de cassation n'est pas liée par les motifs invoqués, mais elle ne peut aller au-delà des conclusions du recourant (art. 277bis PPF). Elle est en revanche liée par les constatations de fait de l'autorité cantonale, sous réserve de la rectification d'une inadvertance manifeste (art. 277bis al. 1 PPF).
4.2 Saisi d'un pourvoi en nullité, le Tribunal fédéral contrôle l'application du droit fédéral (art. 269 PPF) sur la base d'un état de fait définitivement arrêté par l'autorité cantonale (cf. art. 273 al. 1 let. b et 277bis al. 1 PPF). Dès lors, le pourvoi est irrecevable dans la mesure où le recourant allègue de nouveaux faits ou conteste ceux retenus dans la décision attaquée.
4.3 Conformément à l'art. 273 al. 1 let. b PPF, le mémoire de pourvoi doit mentionner les motifs à l'appui des conclusions prises. Il doit succinctement indiquer quelles sont les règles de droit fédéral violées et en quoi consiste cette violation. Pour respecter les exigences minimales de motivation, le recourant doit démontrer concrètement pourquoi, dans le cas d'espèce, le droit fédéral a été violé. Il doit discuter la motivation de la décision rendue en dernière instance cantonale, qui seule peut faire l'objet du pourvoi (cf. art. 268 ch. 1 PPF).
4.3 Conformément à l'art. 273 al. 1 let. b PPF, le mémoire de pourvoi doit mentionner les motifs à l'appui des conclusions prises. Il doit succinctement indiquer quelles sont les règles de droit fédéral violées et en quoi consiste cette violation. Pour respecter les exigences minimales de motivation, le recourant doit démontrer concrètement pourquoi, dans le cas d'espèce, le droit fédéral a été violé. Il doit discuter la motivation de la décision rendue en dernière instance cantonale, qui seule peut faire l'objet du pourvoi (cf. art. 268 ch. 1 PPF).
5. Le recourant conteste avoir utilisé la violence ou un autre moyen de contrainte au sens de l'<ref-law>.
5.1 Se rend coupable de viol, celui qui, notamment en usant de menace ou de violence, en exerçant sur sa victime des pressions d'ordre psychique ou en la mettant hors d'état de résister, aura contraint une personne de sexe féminin à subir l'acte sexuel (<ref-law>). Il y a contrainte lorsque la victime n'est pas consentante, que l'auteur le sait ou accepte cette éventualité et qu'il passe outre en profitant de la situation ou en employant un moyen efficace (<ref-ruling> consid. 2b p. 100 et la jurisprudence citée). L'auteur use de menace lorsque, par ses paroles ou son comportement, il fait volontairement redouter à la victime la survenance d'un préjudice sérieux pour l'amener à céder. Il fait usage de violence lorsqu'il emploie volontairement la force physique sur la personne de la victime afin de la faire céder. La mise hors d'état de résister englobe les cas où l'auteur, pour parvenir à ses fins, rend la victime inconsciente, ce qui le dispense de recourir à la menace ou à la violence pour agir sans le consentement de la victime (<ref-ruling> consid. 2b p. 100). Quant aux pressions d'ordre psychique, elles visent les cas où l'auteur provoque chez la victime des effets d'ordre psychique, tels que la surprise, la frayeur ou le sentiment d'une situation sans espoir, propres à la faire céder (<ref-ruling> consid. 3a/bb p. 111; <ref-ruling> consid. 2b p. 100 et les références citées). En cas de pressions d'ordre psychique, il n'est toutefois pas nécessaire que la victime ait été mise hors d'état de résister (<ref-ruling> consid. 3b p. 158). Ainsi, une situation d'infériorité physique et de dépendance sociale et émotionnelle peut suffire (<ref-ruling> consid. 3b p. 129; <ref-ruling> consid. 3b et c p. 159 ss). Ainsi un climat de psycho-terreur entre époux peut, même sans violence, exercer une influence telle sur la volonté que la victime estime, de manière compréhensible, qu'elle n'a pas de possibilité réelle de résister (<ref-ruling> consid. 3b et c p. 129 ss). Comme l'indique l'adverbe "notamment", la liste des moyens de contrainte énumérés par la loi n'est pas exhaustive (<ref-ruling> consid. 2b p. 100 s. et les références citées). Il faut toutefois que la victime ait été contrainte, ce qui suppose un moyen efficace, c'est-à-dire que la victime ait été placée dans une situation telle qu'il était possible d'accomplir l'acte sans tenir compte de son refus. Il suffit en définitive que, selon les circonstances concrètes, la soumission de la victime soit compréhensible (<ref-ruling> consid. 3a/bb p. 111; <ref-ruling> consid. 3b p. 129; <ref-ruling> consid. 3b p. 159; <ref-ruling> consid. 2b p. 101).
5.2 Il ressort des faits constatés, desquels le recourant n'est pas admis à s'écarter, que ce dernier a attendu la victime à sa sortie du travail et, devant sa réticence à l'accompagner chez lui, l'a tirée par l'avant-bras gauche. Eu égard à la structure de sa personnalité - naïveté certaine, capacité de discernement réduite - la victime n'a pas perçu les intentions malsaines du recourant et n'a pas cherché à fuir. En outre, paralysée par la peur, elle n'a ni appelé au secours ni cherché à se sauver. Arrivé à l'appartement, le recourant a verrouillé la porte et ôté la clef, empêchant ainsi toute fuite de la jeune fille. Il lui a demandé de se coucher sur le lit en la saisissant par le bras. Apeurée, la victime s'est exécutée et le recourant s'est assis sur elle, l'a déshabillée avant de se dévêtir également. Malgré le refus de la jeune fille, qui se débattait des pieds et des mains pour le repousser, le recourant a enfilé un préservatif et l'a pénétrée avant de se retirer, d'ôter le préservatif et d'éjaculer sur le lit. Il a également été admis que le recourant voyait sa victime effrayée, qu'il avait déjà menacé de la taper auparavant et savait qu'il avait un certain ascendant sur elle. Dès lors, le recourant a non seulement usé de contrainte en profitant de sa force et sa supériorité physique pour immobiliser sa victime, mais a encore exercé sur elle une pression psychique, l'effrayant et exploitant cette peur et l'infériorité cognitive de la jeune fille, cette dernière étant de par sa personnalité démunie dans la confrontation et les tensions et, en cas de stress et de surstimulation, perdant ses moyens et ne parvenant plus à fonctionner adéquatement. Il a par ces moyens, qui, compte tenu de la personnalité de la victime, sont suffisamment intensifs, obtenu de celle-ci qu'elle subisse l'acte sexuel auquel elle n'a pas consenti et la soumission de cette dernière apparaît, dans les circonstances données, compréhensible. Dans la mesure où le recourant conteste qu'il y ait eu pénétration, il s'écarte des faits constatés, ce qui est irrecevable. Les autres éléments constitutifs de l'infraction étant réunis et n'étant pas contestés par le recourant, sa condamnation ne viole donc pas le droit fédéral.
5.2 Il ressort des faits constatés, desquels le recourant n'est pas admis à s'écarter, que ce dernier a attendu la victime à sa sortie du travail et, devant sa réticence à l'accompagner chez lui, l'a tirée par l'avant-bras gauche. Eu égard à la structure de sa personnalité - naïveté certaine, capacité de discernement réduite - la victime n'a pas perçu les intentions malsaines du recourant et n'a pas cherché à fuir. En outre, paralysée par la peur, elle n'a ni appelé au secours ni cherché à se sauver. Arrivé à l'appartement, le recourant a verrouillé la porte et ôté la clef, empêchant ainsi toute fuite de la jeune fille. Il lui a demandé de se coucher sur le lit en la saisissant par le bras. Apeurée, la victime s'est exécutée et le recourant s'est assis sur elle, l'a déshabillée avant de se dévêtir également. Malgré le refus de la jeune fille, qui se débattait des pieds et des mains pour le repousser, le recourant a enfilé un préservatif et l'a pénétrée avant de se retirer, d'ôter le préservatif et d'éjaculer sur le lit. Il a également été admis que le recourant voyait sa victime effrayée, qu'il avait déjà menacé de la taper auparavant et savait qu'il avait un certain ascendant sur elle. Dès lors, le recourant a non seulement usé de contrainte en profitant de sa force et sa supériorité physique pour immobiliser sa victime, mais a encore exercé sur elle une pression psychique, l'effrayant et exploitant cette peur et l'infériorité cognitive de la jeune fille, cette dernière étant de par sa personnalité démunie dans la confrontation et les tensions et, en cas de stress et de surstimulation, perdant ses moyens et ne parvenant plus à fonctionner adéquatement. Il a par ces moyens, qui, compte tenu de la personnalité de la victime, sont suffisamment intensifs, obtenu de celle-ci qu'elle subisse l'acte sexuel auquel elle n'a pas consenti et la soumission de cette dernière apparaît, dans les circonstances données, compréhensible. Dans la mesure où le recourant conteste qu'il y ait eu pénétration, il s'écarte des faits constatés, ce qui est irrecevable. Les autres éléments constitutifs de l'infraction étant réunis et n'étant pas contestés par le recourant, sa condamnation ne viole donc pas le droit fédéral.
6. Le recourant conteste encore sa condamnation pour extorsion. Il conteste avoir menacé sa victime d'un dommage sérieux.
6.1 L'<ref-law> réprime le comportement de celui qui, dans le dessein de se procurer ou de procurer à un tiers un enrichissement illégitime, aura déterminé une personne à des actes préjudiciables à ses intérêts pécuniaires ou à ceux d'un tiers, en usant de violence ou en la menaçant d'un dommage sérieux. Pour que cette infraction soit objectivement réalisée, il faut que l'auteur, par un moyen de contrainte, ait déterminé une personne à accomplir un acte portant atteinte à son patrimoine ou à celui d'un tiers. La loi prévoit deux moyens de contrainte: la violence et la menace d'un dommage sérieux. La menace est un moyen de pression psychologique. Elle peut être expresse ou tacite et être signifiée par n'importe quel moyen. Quant au dommage, il peut toucher n'importe quel intérêt juridiquement protégé. Il faut toutefois qu'il soit sérieux, c'est-à-dire que la perspective de l'inconvénient soit de nature à entraver le destinataire dans sa liberté de décision. La question doit être tranchée en fonction de critères objectifs, c'est-à-dire non pas d'après les réactions du destinataire d'espèce, mais en recherchant si la perspective de l'inconvénient est propre à amener un destinataire raisonnable à adopter un comportement qu'il n'aurait pas eu s'il avait joui de toute sa liberté de décision (cf. <ref-ruling> consid. 1a p. 325 s.; <ref-ruling> consid. 2a/aa p. 19 et les arrêts cités). L'usage de la contrainte doit avoir déterminé la personne visée à accomplir un acte préjudiciable à ses intérêts pécuniaires ou à ceux d'un tiers. Cela implique d'abord que la personne visée ait conservé une certaine liberté de choix et se lèse elle-même ou lèse autrui par son acte (Corboz, Les infractions en droit suisse, vol. I, Berne 2002, <ref-law> n° 18 et <ref-law> n° 28; Stratenwerth, Schweizerisches Strafrecht, Partie spéciale I, 5ème éd. Berne 1995, § 17 n° 6 s. et § 15 n° 31 s.).
6.2 Dans le cas particulier, il ressort des faits constatés que le recourant a suivi la victime jusqu'à l'endroit où elle travaillait et qu'il a menacé de la frapper si elle ne faisait pas ce qu'il voulait. Il lui a demandé 10 francs et, apeurée, la jeune fille s'est exécutée. Par la suite le recourant lui a encore réclamé de l'argent à plusieurs reprises, lors de rencontres devant son lieu de travail, en ville ou à la gare de Monthey, en menaçant de la "taper". Sous la peur, la victime finissait toujours par lui obéir et lui remettre des petites sommes d'argent. Ainsi, le recourant a déterminé sa victime à lui remettre de l'argent en la menaçant d'un dommage à l'intégrité corporelle. La menace d'une agression physique était objectivement sérieuse et de nature à entraver la victime dans sa liberté de décision. Les autres éléments constitutifs de l'infraction étant réalisés et non contestés par le recourant, la condamnation du recourant ne viole pas le droit fédéral.
6.2 Dans le cas particulier, il ressort des faits constatés que le recourant a suivi la victime jusqu'à l'endroit où elle travaillait et qu'il a menacé de la frapper si elle ne faisait pas ce qu'il voulait. Il lui a demandé 10 francs et, apeurée, la jeune fille s'est exécutée. Par la suite le recourant lui a encore réclamé de l'argent à plusieurs reprises, lors de rencontres devant son lieu de travail, en ville ou à la gare de Monthey, en menaçant de la "taper". Sous la peur, la victime finissait toujours par lui obéir et lui remettre des petites sommes d'argent. Ainsi, le recourant a déterminé sa victime à lui remettre de l'argent en la menaçant d'un dommage à l'intégrité corporelle. La menace d'une agression physique était objectivement sérieuse et de nature à entraver la victime dans sa liberté de décision. Les autres éléments constitutifs de l'infraction étant réalisés et non contestés par le recourant, la condamnation du recourant ne viole pas le droit fédéral.
7. Le recourant se plaint encore d'une violation de l'<ref-law> en ce que la peine qui lui a été infligée serait excessive.
7.1 Pour fixer la peine, le juge dispose d'un large pouvoir d'appréciation. Un pourvoi en nullité portant sur la quotité de la peine ne peut donc être admis que si la sanction à été fixée en dehors du cadre légal, si elle est fondée sur des critères étrangers à l'<ref-law>, si les éléments d'appréciation prévus par cette disposition n'ont pas été pris en compte ou enfin si la peine apparaît exagérément sévère ou clémente au point que l'on doive parler d'un abus du pouvoir d'appréciation (<ref-ruling> consid. 6.1 p. 20 s. et les arrêts cités).
Les éléments pertinents pour la fixation de la peine, qui ont été exposés de manière détaillée dans les <ref-ruling> consid. 1 et 116 IV 288 consid. 2a, ont été rappelés récemment dans l'<ref-ruling> consid. 6.1 p. 20 s. ainsi que les exigences quant à la motivation de la peine dans l'<ref-ruling> consid. 2c p. 104 s., auxquels on peut donc se référer.
7.2 Le recourant reproche tout d'abord aux premiers juges de ne pas avoir tenu compte de son absence d'antécédents en Algérie. Cependant, il a été relevé que le casier judiciaire du recourant ne mentionnait plus aucune inscription le 21 août 2006. Il a été rappelé qu'il avait été condamné à 2 reprises en Suisse pour infraction à la loi fédérale sur le séjour et l'établissement des étrangers. Si son casier judiciaire algérien avait fait état de condamnations, elles auraient également été mentionnées, de telle sorte qu'on doit admettre a contrario qu'il a été tenu compte du fait qu'il n'en mentionne pas.
Le recourant prétend encore que la peine qui lui a été infligée dépasse largement celles prononcées dans des cas similaires. Ce grief est infondé. En effet, comme la jurisprudence a déjà eu l'occasion de le souligner, eu égard aux nombreux paramètres qui interviennent dans la fixation de la peine, une comparaison avec des affaires concernant d'autres accusés et des faits différents est d'emblée délicate et généralement stérile dès lors qu'il existe presque toujours des différences entre les circonstances, objectives et subjectives, que le juge doit prendre en considération dans chacun des cas (<ref-ruling> consid. 3a p. 144; <ref-ruling>). Il ne suffit notamment pas que le recourant puisse citer l'un ou l'autre cas où une peine particulièrement clémente a été fixée pour prétendre à un droit à l'égalité de traitement (<ref-ruling> consid. 3a p. 144 et les arrêts cités). Il faut au reste rappeler que le principe de la légalité prime sur celui de l'égalité (<ref-ruling>, consid. 2c p. 47). Au vu de cette jurisprudence, c'est en vain que le recourant affirme que des peines inférieures ou égales auraient été prononcées dans des causes où les faits reprochés, qui ne sont au demeurant pas seuls déterminants pour fixer la peine, étaient semblables ou bien plus graves que ceux dont il doit répondre.
La peine a été fixée dans le cadre légal, en suivant les critères posés par l'<ref-law> et sans se laisser guider par des considérations étrangères à cette disposition. La culpabilité du recourant est grave. Il n'a pas hésité à s'en prendre à une jeune fille fragile, timide et effacée, profitant de la situation d'infériorité de celle-ci pour abuser d'elle et lui soutirer le peu d'argent dont elle disposait. Logé par des compatriotes, il a séjourné sur le territoire vaudois de manière illégale pendant près de deux ans. Ses antécédents comportent deux condamnations pour infractions à la LSEE. Il ne bénéficie d'aucune circonstance atténuante. En revanche la circonstance aggravante du concours et celle de la récidive sont réalisées. Dans ces conditions, la peine prononcée, de trois ans de réclusion, quand bien même elle paraît sévère, ne procède pas d'un abus du large pouvoir d'appréciation conféré à l'autorité cantonale.
Le pourvoi ne peut qu'être rejeté dans la mesure où il est recevable.
Le pourvoi ne peut qu'être rejeté dans la mesure où il est recevable.
8. Comme les recours paraissaient d'emblée voués à l'échec, la requête d'assistance judiciaire doit être rejetée (art. 152 al. 1 OJ). Le recourant, qui succombe, supportera les frais de la cause, lesquels seront fixés en tenant compte de sa situation financière. Il n'y a pas lieu d'allouer d'indemnité à la victime, qui n'est pas intervenue dans la procédure.

Par ces motifs, le Tribunal fédéral prononce:
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours de droit public est rejeté dans la mesure où il est recevable.
1. Le recours de droit public est rejeté dans la mesure où il est recevable.
2. Le pourvoi en nullité est rejeté dans la mesure où il est recevable.
2. Le pourvoi en nullité est rejeté dans la mesure où il est recevable.
3. La requête d'assistance judiciaire est rejetée.
3. La requête d'assistance judiciaire est rejetée.
4. Un émolument judiciaire de 1600 francs est mis à la charge du recourant.
4. Un émolument judiciaire de 1600 francs est mis à la charge du recourant.
5. Le présent arrêt est communiqué en copie aux mandataires des parties, à la Cour pénale II du Tribunal cantonal et au Ministère public du canton du Valais.
Lausanne, le 2 mars 2007
Au nom de la Cour de cassation pénale
du Tribunal fédéral suisse
Le président: La greffière: